Witam,
Mam pytanie dotyczące algorytmu Dijkstry. Zawsze używałem następującej implementacji w c++:
struct edge //potrzebne tylko dla std::set poniżej
{
int vertex;
unsigned long weight;
edge(int v, unsigned long wt) : vertex(v), weight(wt) { }
bool operator<(const edge& e2) const
{
return weight < e2.weight;
}
};
void dijkstra_algorithm()
{
for(int i = 0 ; i < G.V() ; ++i)
{
wt[i] = ULONG_MAX; //długość najkr. ścieżki od wierzchołka start. do i
spt[i] = 0; //ostatnia krawędź prowadząca do wierzchołka i
}
int v = start_vertex;
wt[v] = 0;
std::set<edge> vertex_queue;
vertex_queue.insert(edge(v, wt[v]));
while(!vertex_queue.empty())
{
v = vertex_queue.begin()->vertex;
vertex_queue.erase(vertex_queue.begin());
DenseWeightedGRAPH::adjIterator A(G, v);
for(Weighted_edge* e = A.beg() ; !A.end() ; e = A.nxt()) //przetwarzamy każdego sąsiada
//wierzchołka v, sąsiad jest zapisany jako klasa Weighted_edge
{
unsigned long P = wt[v] + e->wt(); //wt() zwraca wagę krawędzi
int w = e->other(v); //ta funkcja zwraca wierzchołek leżący naprzeciwko wierzchołka "v" w krawędzi "e"
if(P < wt[w])
{
vertex_queue.erase(edge(w, wt[w]));
wt[w] = P;
spt[w] = e;
vertex_queue.insert(edge(w, wt[w]));
}
}
}
}
Ale gdy odpaliłem jedno zadanie na pewnej sprawdzarce online, długo szukany problem tkwił w tym algorytmie, który raczej mnie nie zawodził. Powyższy program nie przechodził największego testu, więc ciężko było mi prześledzić jego działanie.
W necie znalazłem inną implementację Dijkstry i zmodyfikowałem ją pod moją implementację grafu:
void dijkstra_algorithm()
{
for(int i = 0 ; i < G.V() ; ++i)
{
wt[i] = ULONG_MAX;
spt[i] = 0;
}
int v = start_vertex;
wt[v] = 0;
bool visit[MAX_VERTICES] = { false };
queue<int> q;
q.push(v);
while (!q.empty())
{
v = q.front();
q.pop();
visit[v] = false;
DenseWeightedGRAPH::adjIterator A(G, v);
for(Weighted_edge* e = A.beg() ; !A.end() ; e = A.nxt())
{
unsigned long P = wt[v] + e->wt();
int w = e->other(v);
if(P < wt[w])
{
wt[w] = P;
spt[w] = e;
if(!visit[w])
{
visit[w] = true;
q.push(w);
}
}
}
}
}
Jak widać jest tam jakaś tablica odwiedzonych i kolejka zamiast kolejki priorytetowej w formie std::set.
Dzięki takiemu algorytmowi mój program przechodzi pewien duży test, ale dlaczego mój pierwszy algorytm nie działa? Ten drugi wydaje się być nawet prostszy, ale nigdy się nad takim nie zastanawiałem bo w definicji algorytmu Dijkstry zawsze pojawia się słowo "kolejka priorytetowa". Z wikipedii, jako jeden z kroków:
Utwórz kolejkę priorytetową Q wszystkich wierzchołków grafu. Priorytetem kolejki jest aktualnie wyliczona odległość od wierzchołka źródłowego s.
(Natomiast pierwszy algorytm wziąłem jakiś czas temu z http://rosettacode.org/wiki/Dijkstra's_algorithm#C.2B.2B i zmodyfikowałem pod moją implementację grafu - wydaje mi się że zrobiłem to dobrze zgodnie z definicją tego algorytmu.)
Czy w pierwszym algorytmie jest jakiekolwiek wąskie gardło?