So speichern Sie den kürzesten Pfad im Dijkstra-Algorithmus

Question

Also zuerst definieren wir Dijkstra Algorithmus:
Dijkstra-Algorithmus findet Single-Source kürzeste Wege in einem gerichteten Graphen mit nicht-negativen Kantengewichten.
Ich möchte wissen, wie kann ich den kürzesten Pfad Form s zu t mit Dijkstra Algorithmus speichern.
Ich suchte auf Google, aber ich konnte nichts bestimmtes finden; Ich habe auch den Dijkstra-Algorithmus geändert, aber ich konnte keine Antwort bekommen. Wie kann ich den kürzesten Weg von s nach t mit Dijkstra speichern?
Ich weiß, meine Frage ist einfach und unprofessionell, aber jede Hilfe wäre willkommen. Danke, dass du meine Frage bedenkst.

Answer 1

Wenn man sich die aus dem Wikipedia-Link pseudocode schauen Sie gaben, werden Sie dort eine Reihe sehen in prev[] genannt. Dieses Array enthält für jeden Knoten v in dem Diagramm, den vorherigen Knoten u in dem kürzesten Pfad zwischen dem Quellknoten s und v. (. Dieses Array wird auch als Vorgänger oder Mutter array)

Mit anderen Worten, der kürzeste Weg zwischen s und v ist:

s -> u -> v 
where u = prev[v] 

Der Weg von s bis u möglicherweise mehrere Knoten dazwischen haben, um den Pfad von s bis v zu rekonstruieren, die Sie gerade auf dem Weg zu Fuß zurück durch der den Code-Snippet unter dem Haupt Pseudo-Code mit prev[] Array definiert (Ziel ist v):

1 S ← empty sequence 
2 u ← target 
3 while prev[u] is defined:     // Construct the shortest path with a stack S 
4  insert u at the beginning of S   // Push the vertex onto the stack 
5  u ← prev[u]        // Traverse from target to source 
6 end while 

Answer 2

Die meisten Bibliotheken, die diesen Algorithmus verwenden, geben Ihnen wahrscheinlich einen Weg, dies zu tun. Aber behalten Sie im Allgemeinen den Weg zu jedem Knoten im Auge. Dh gibt Sie jeden Knoten ein attrribute shortestPathToNode, in dem Sie speichern die Liste der Knoten

Answer 3

Ein extrem kurzer Weg, dies zu tun, ist die Rekursion zu verwenden und ein "Eltern-Array". Wenn Sie alle Eltern der Punkte auf -1 initialisieren und dann, wenn Sie Dijkstra's vervollständigen, das Eltern-Array aktualisieren, können Sie von jedem beliebigen Punkt aus zurückspringen, bis Sie zur Quelle gelangen und den Pfad ausdrucken. Hier ist eine sehr kurze und einfache Rekursion Schnipsel zu verstehen:

// Function to print shortest path from source to j using parent array 
void path(parent array, int j) 
{ 
    // Base Case : If j is source 
    if (jth element of parent is -1) return; 
  
    path(parent, jth element of parent); 
  print j; 
} 

Beachten Sie, dass anstelle des Druckens „j“ aus, können Sie es in einem globalen Vektor speichern kann (oder einem anderen Datentyp für Sprachen, die nicht C bezogen sind) für späteren Gebrauch.