Dijkstra - Kürzesten Weg berechnen
-
Hallo zusammen,
mittlerweile habe ich meinen Dijkstra-Algorithmus soweit, dass
für Distanzgraphen die einzelnen Distanzen bestimmt werden.So nun zu meinem Problem:
Ich möchte den Algorithmus nun noch so ergänzen, dass nicht nur die Distanzen
errechnet werden, sondern der zugehörige kürzeste Weg bestimmt wird.Meine Idee:
Ich füge einen Vektor 'prev' (einen Vektor von Knoten) hinzu, in dem der
jeweilige Vorgänger immer gespeichert wird.
Distanzupdate = Vorgängerupdate. Zur Weg-Berechnung wird dann einfach der Vektor
benutzt, indem man alle Knotendistanzen welche auf dem Weg liegen addiert.Der bisherige Code:
(In der dijkstra.cpp ist lediglich die Klasse 'DistGraph' implementiert,
mitsamt Attributen und Methoden.)#include "dijkstra.cpp" using namespace std; typedef int VertexT; typedef std::pair<VertexT,VertexT> EdgeT; typedef double CostT; void dijkstra(const DistGraph& g, VertexT& v0, vector<CostT>& D){ set<VertexT> R; int N= g.NumVertices; for(VertexT i=0; i<N; i++) { R.insert(i); } R.erase(v0); D.resize(N,infty); D[v0]=0 ; for(set<VertexT>::iterator it=R.begin(); it != R.end(); it++) { D[*it]=g.Cost(v0, *it); } while (!R.empty()){ double min=infty; VertexT vmin= -1; for(set<VertexT>::iterator it=R.begin(); it != R.end(); it++){ if (D[*it] < min){ min=D[*it]; vmin= *it; } } R.erase(vmin); for(set<VertexT>::iterator it=R.begin(); it != R.end(); it++){ if (D[*it] > D[vmin] + g.Cost(vmin,*it)){ D[*it]=D[vmin] + g.Cost(vmin,*it); } } }Mir ist nur nicht ganz klar, an welchen Stellen ich das Updaten implementieren muss
Sobald mein Vektor aus Vorgängern einmal bestimmt ist, iteriere ich einfach wieder um die Summe der Distanzen (den kürzesten Weg) zu ermitteln.Bin für jeden Tipp und Ratschlag dankbar
-
In dem if der Schleife über die Nachbarn des aktuell betrachtenden Knotens. Also in Zeile ~35. Dort setzt du den Vorgänger des Knotens.
Dein Code sieht etwas komisch aus, ich bin mir nicht sicher ob der das macht was er soll, da ich zuviel Zeit in die richtige Einarbeitung jetzt aufwenden müsste.
Auf jedenfall ist mir unerklärlich wofür du die zweite Schleife brauchst? Dort setzt du die Kosten für alle Knoten zum Startknoten?
Dann einen Tipp: Djistkra und auch A* sind im Prinzip eine Breitensuche, bei der die Knoten anders angeordnet werden, bei der Bearbeitung.
Während eine Breitensuche alle Kinder von einem aktuellen Knoten an eine Queue anhängt, sortiert der Dijkstra nach dem minimalen bisher zurückgelegten Weg. A* ist dann die Verallgemeinerung und lässt noch die verbleibenden Kosten in diese Rechnung oder Sortierung mit einfließen.
Auf jeden Fall sind die Standarddatenstrukturen für die Breitensuche eine Queue und für Dijkstra und A+ eine Priority Queue. Und eben diese gibt es auch beide in der C++ Standardbibliothek (std::priority_queue). Nutz die doch, anstatt immer über dein ganzes Set (also die OpenList) zu iterieren. Denn eben diese Struktur ist maßgeblich für die Laufzeit verantwortlich.
-
Was du machen willst, nennt sich Backtracking falls du mal danach suchen willst. Im Prinzip sollte ueberall eine Referenz sein, aus welcher Richtung man kommt, wenn man dem kuerzesten Weg folgt. Das geht zum Beispiel wie du Vorschlaegst in dem man ein "prev" abspeichert, womit man sich am Ende zurueckhangelt.
-
Danke für die Hilfe !
Habe es dann hinbekommenFertiger Code schaut wie folgt aus (und funktioniert mit meinen Distanzgraphen):
void dijkstra(const DistGraph& g, VertexT& v0, vector<CostT>& D, vector<VertexT>& prev){ set<VertexT> R; int N= g.GetNumVertices(); for(VertexT i=0; i<N; i++) { R.insert(i); } R.erase(v0); D.resize(N,0); D[v0]=0 ; prev.resize(N,-1); //Größe von prev festlegen for(set<VertexT>::iterator it=R.begin(); it != R.end(); it++) { D[*it]=g.Cost(v0, *it); if(D[*it] != infty){ prev[*it]=v0; //Ziele, die direkt von v0 erreichbar sind } } while (!R.empty()){ double min=infty; VertexT vmin= -1; for(set<VertexT>::iterator it=R.begin(); it != R.end(); it++){ if (D[*it] < min){ min=D[*it]; vmin= *it; } } if (min>=infty) return; R.erase(vmin); for(set<VertexT>::iterator it=R.begin(); it != R.end(); it++){ if (D[*it] > D[vmin] + g.Cost(vmin,*it)){ D[*it]=D[vmin] + g.Cost(vmin,*it); prev[*it]=vmin;}//Distanzupdate = Vorgängerupdate } } }Thema kann dann gerne geschlossen werden.
-
TGGC schrieb:
Was du machen willst, nennt sich Backtracking
Nö, absolut nicht.
-
volkard schrieb:
TGGC schrieb:
Was du machen willst, nennt sich Backtracking
Nö, absolut nicht.
Doch.
-
Jester schrieb:
volkard schrieb:
TGGC schrieb:
Was du machen willst, nennt sich Backtracking
Nö, absolut nicht.
Doch.
Pass das zu "Die Tiefensuche und somit auch Backtracking haben im schlechtesten Fall mit O(z^N) eine exponentielle Laufzeit."?
http://de.wikipedia.org/wiki/Backtracking#Zeitkomplexit.C3.A4t
Oder zu "Wenn absehbar ist, dass eine Teillösung nicht zu einer endgültigen Lösung führen kann, wird der letzte Schritt beziehungsweise werden die letzten Schritte zurückgenommen, und es werden stattdessen alternative Wege probiert."?Dijkstra flutet doch einfach, daß man sich dabei Infos speichern kannm um schnell den ganzen Weg zu finden, hat doch nix mit Backtracking zu tun. Ich gehe mal nicht davon aus, daß Dueinen Verzweigungsgrad z=1 meinst, dann ist alles auf der Welt mit Backtracking.
-
volkard schrieb:
Dijkstra flutet doch einfach, daß man sich dabei Infos speichern kannm um schnell den ganzen Weg zu finden, hat doch nix mit Backtracking zu tun. Ich gehe mal nicht davon aus, daß Dueinen Verzweigungsgrad z=1 meinst, dann ist alles auf der Welt mit Backtracking.
Das rückwärts aufsammeln der Information aus welchen Teillösungen sich eine Lösung in einem dynamischen Programm zusammensetzt, heißt ebenfalls Backtracking. Dynamische Programmierung ist ein eng verwandtes Konzept zum Backtracking, nur dass es dort eben gelingt die Teilbäume des Suchbaums geschickt übereinander zu legen, wodurch man einen effizienten Algorithmus erhält. In diesem Fall weil man sich pro Knoten eben nur den kürzesten Weg und nicht alle Wege merken muss. Insofern finde ich es nicht verwunderlich, dass da auch Nomenklatur mit übernommen wird.
