Ich lese den Ansatz von Wikipedia , um den kurzen Pfad s / w zwei gegeben zu drucken Punkte in einer Grafik durch Ändern des Floyd Warshall-Algorithmus. Ich habe dies codiert, aber es gibt nicht die erwartete Ausgabe:
Initialisiert alle Elemente in minimumDistanceMatrix[i][j] für die entsprechenden Gewichtungen im Diagramm und für alle Elemente in der Matrix shortestPathCalculatorMatrix [i][j] bis -1.
Dann:
%Vor%Dann:
%Vor% P.S: pathCityList ist ein Vektor, von dem angenommen wird, dass er leer ist, bevor ein Aufruf von findShortestPathListBetween erfolgt. Am Ende dieses Aufrufs enthält dieser Vektor alle dazwischenliegenden Knoten.
Kann jemand darauf hinweisen, wo ich vielleicht falsch liege?
Der Wikipedia-Artikel ist schrecklich. Abgesehen davon, dass es (meiner Meinung nach) die kanonische Form des Floyd-Warshall-Algorithmus falsch repräsentiert, präsentiert es einen fehlerhaften Pseudocode.
Es ist viel einfacher (und direkter), nicht über Indizes, sondern über Eckpunkte zu iterieren. Darüber hinaus muss jeder Vorgänger (normalerweise mit π , nicht mit next ) auf seinen Vorgänger und nicht auf den aktuellen temporären Scheitelpunkt verweisen.
In diesem Sinne können wir ihren zerbrochenen Pseudocode beheben.
%Vor%Beachten Sie, dass ich die drei verschachtelten Schleifen geändert habe, um über Scheitelpunkte und nicht über Indizes zu iterieren, und ich habe die letzte Zeile so korrigiert, dass sie sich auf den vorherigen Knoten und nicht auf einen Zwischenknoten bezieht.
Eine Erklärung, warum das korrekt ist und wie die Vorgängermatrix funktioniert, kann auf Algoritmy.net gefunden werden .
Das obige erfordert eine Initialisierung. Glücklicherweise ist das einfach, da wir bereits den ersten Vorgänger jedes Knotens kennen: Wenn es einen direkten Pfad von i nach j gibt, dann ist i der Vorgänger von j . Wenn es keinen direkten Pfad gibt, dann gibt es keinen Vorgänger.
NIL ist nur ein Platzhalter für jeden Nicht-Vertex-Wert. In objektorientiertem Code wäre dies normalerweise ein null Verweis / Zeiger. Wenn der Graph als eine Adjazenzmatrix implementiert wird, kann er irgendein Index sein, der nicht einem Eckpunkt entspricht, z. -1 oder | V | +1.
Sie bieten auch eine korrigierte Pfadrekonstruktion:
%Vor%Tags und Links algorithm c++ shortest-path floyd-warshall