dijkstra algo
-
Hi,
ich habe eine frage zum dijkstra algo fuer einen undirected graph.
auf wikipedia ([url]http://en.wikipedia.org/wiki/Dijkstra's_algorithm[/url]) wird der algo so beschrieben, dass man ein array visited braucht.
"A visited node will never be checked again."
warum wird dann selber im pseudo code (mit priority queue) kein array visited verwendet?
mir fehlt da irgendwie ein:
[/code]
Node u = PQ.top(); // Remove and return best vertex
if(visited[u.target]) continue;
visited[u.target] = true;peudo code: [code] 1 function Dijkstra(Graph, source): 2 dist[source] := 0 // Initializations 3 for each vertex v in Graph: 4 if v ≠ source 5 dist[v] := infinity // Unknown distance from source to v 6 previous[v] := undefined // Predecessor of v 7 end if 8 PQ.add_with_priority(v,dist[v]) 9 end for 10 11 12 while PQ is not empty: // The main loop 13 u := PQ.extract_min() // Remove and return best vertex 14 for each neighbor v of u: // where v has not yet been removed from PQ. 15 alt = dist[u] + length(u, v) 16 if alt < dist[v] // Relax the edge (u,v) 17 dist[v] := alt 18 previous[v] := u 19 PQ.decrease_priority(v,alt) 20 end if 21 end for 22 end while 23 return previous[]
-
Und die C++ Frage ist jetzt wo?
-
c++coder11 schrieb:
auf wikipedia ([url]http://en.wikipedia.org/wiki/Dijkstra's_algorithm[/url]) wird der algo so beschrieben, dass man ein array visited braucht.
"A visited node will never be checked again."
Wie liest du denn da heraus, dass du ein Array der besuchten Nodes brauchst? Im Pseudocode und in der Beschreibung wird sogar ausdrücklich gesagt, dass ein Node dadurch "visited" wird, dass er nicht mehr in der Menge der unbesuchten Nodes ist.
Beachte auch, dass der abstrakte Begriff einer Menge nicht unbedingt ein Array bezeichnet. Wenn man dem Begriff eine konkrete Datenstruktur zuschreiben möchte, dann wäre der erste Gedanke auch eher ein set als ein Array ("Menge" heißt im Englischen "set"). Was nicht unbedingt heißen muss, dass die Datenstruktur set unbedingt die beste Wahl ist, aber die naheliegendste (In der Beschreibung des Algorithmus ist mit "set" irgendeine abstrakte Struktur gemeint, bei der man feststellen kann, ob sie einen Wert enthält und welche Werte sie enthält - etwas was durchaus auch auf ein Array zutrifft).
-
Dieser Thread wurde von Moderator/in SeppJ aus dem Forum C++ (auch C++0x und C++11) in das Forum Rund um die Programmierung verschoben.
Im Zweifelsfall bitte auch folgende Hinweise beachten:
C/C++ Forum :: FAQ - Sonstiges :: Wohin mit meiner Frage?Dieses Posting wurde automatisch erzeugt.
-
wird denn jeder knoten im graph nur 1 mal besucht wenn ich dijkstra aufrufe?
-
c++coder11 schrieb:
wird denn jeder knoten im graph nur 1 mal besucht wenn ich dijkstra aufrufe?
ist es nicht schon der shortest path beim ersten besuch?
-
c++coder11 schrieb:
wird denn jeder knoten im graph nur 1 mal besucht wenn ich dijkstra aufrufe?
Nein. Es kann sein, dass ein Knoten ein Nachbar vom Start ist, aber sehr teuer zu erreichen ist. Nun kann es passieren, dass dieser (teure) Knoten über mehrere andere Umwege billiger zuerreichen ist. Die Kosten für den Knoten werden geupdatet (eventuell passiert das sogar nochmal, dass es noch einen kürzeren Weg zu dem Knoten gibt).
Dijkstra ist im Prinzip eine angepasste Breitensuche.
Die Breitensuche guckt sich (ausgehend vom Start) nacheinander alle Nachbarknoten an, und zwar in der Reihenfolge, in der die Knoten der Queue (ich nenne sie immer OpenQueue oder OpenList) hinzugefügt werden. Bei der Breitensuche werden alle adjazenten Knoten der OpenList angehängt.Dijkstra geht an der Stelle einen Schritt weiter und ordnet diese Knoten noch nach den bisherigen Kosten zu jedem Knoten. Und expandiert so jeweils den mit den kleinsten Kosten.
Der A*-Algorithmus geht noch einen Schritt weiter. Dabei werden die Knoten in der OpenList nach den bisherigen (echten/realen) Kosten plus einem Schätzwert, der angibt, wie viel Kosten noch ungefähr nötig sind, um das Ziel zu erreichen, geordnet.
Dijkstra kann man daher als Spezialfall des A*-Algorithmus ansehen, oder umgekehrt: A* ist die Verallgemeinerung von Dijkstra.
Der anschauliche Unterschied ist im Prinzip, dass sich bei einer Dijkstra-Suche der Suchraum radial um den Start ausbreitet, während der Heuristikwert von A* die Suche lenkt und somit einen Kegel in Richtung des Ziels bildet.
-
wenn man immer den guenstigsten weg zuerst (rekursiv) evaluiert, dann sollte man doch keinen knoten mehr als einmal besuchen muessen, oder uebersehe ich was? (aber ich hab mir den wiki code nicht angeschaut)
-
Moment, wir müssen da differenzieren:
Jeder Knoten wird maximal einmal besucht oder expandiert. Expandieren (oder besuchen) bedeutet in dem Fall, dass der Knoten das Subjekt eienr Betrachtung ist. D.h. seine Nachbarn werden der openList hinzugefügt.
Dieses Hinzufügen der Nachbarn kann jedoch auch mehrmals pro Knoten geschehen (das ist das was ich oben meinte). In dem Fall kann man das mehrmalige Hinzufügen auch Update nennen. Was nun konkret schneller ist, ist wiederum einen kurzen Gedanken wert
Ich habe in einer Implementierung von mir Knotenkandidaten auch mehrmals der Openlist hinzugefügt, sie bei wiederholter Betrachtung dann jedoch wieder verworfen. Das war effizienter als in einer std::priority_queue den entsprechenden Knoten zu suchen und upzudaten.Beim A*-Algorithmus kann es jedoch passieren, dass Knoten mehrmals expandiert werden können. Das passiert dann, wenn die zugrundeliegende Heuristik bestimmte Eigenschaften hat (welche das sind, weis ich im Kopf grad nicht mehr, müsste ich in meiner Abschlussarbeit nachschauen).
-
Sie darf Distanzen nicht unterschätzen.
Man muss die visited knoten nicht explizit mitspeichern, weil ein besuchter knoten ja seinen korrekten hat. Und den hat er in dem Moment bekommen als er aus der Queue entnommen wurde. Da jeder knoten nur einmal in die Queue kommt, kann kein knoten der schon entnommen wurde nochmal besucht werden.
