Änderung von Dijkstras Algorithmus

Question

Ich spiele gerade mit dem sehr berühmten Dijkstra Algorithmus und bin ein wenig fest. Ich versuche, den Pseudocode zu modifizieren, um eine Eingabe von BOTH der Quelle und des Ziels zu machen, um den SHORTEST-Pfad zwischen den zwei Vertices in einem implementierten Graph zu finden. Ich möchte die Eingänge SOURCE und DEST als Stringwerte verwenden. Ich versuche auch zu modifizieren, also ist die Eingabe einfach die Liste KÜRZERER WEG. Irgendwelche Ideen, wie ich den Algorithmus modifizieren kann, um das zu erreichen?

1: function Dijkstra(Graph, source): 
2: for each vertex v in Graph: // Initialization 
3: dist[v] := infinity // initial distance from source to vertex v is set to infinite 
4: previous[v] := undefined // Previous node in optimal path from source 
5: dist[source] := 0 // Distance from source to source 
6: Q := the set of all nodes in Graph // all nodes in the graph are unoptimized - thus are in Q 
7: while Q is not empty: // main loop 
8: u := node in Q with smallest dist[ ] 
9: remove u from Q 
10: for each neighbor v of u: // where v has not yet been removed from Q. 
11: alt := dist[u] + dist_between(u, v) 
12: if alt < dist[v] // Relax (u,v) 
13: dist[v] := alt 
14: previous[v] := u 
15: return previous[ ] 

Answer 1

Fügen Sie einfach DESTINATION als Argument hinzu, das Ihre Funktion als Eingabe akzeptiert, und setzen Sie den Algorithmus wie gewohnt fort. Entfernen Sie einfach die letzte Zeile

return previous[ ] 

Und die folgenden Zeilen hinzufügen, die nur für die Knoten in dem kürzesten Weg die vorherige [] Liste zugreift. Sie starten diese Traversal vom DEST Knoten und gehen, bis Sie SOURCE erreichen

x := DEST 
shortest_path := [] 
while x is not equal to SOURCE: 
     shortest_path.add(x) 
     x := previous[x] 
shortest_path.add(x) //finally add the SOURCE outside the loop 
return shortest_path[] 

Um SOURCE und DEST als String-Werte zu nehmen, müssen Sie eine Routine, die einen String und gibt einen Knoten, der mit dem Wert in diesem Graph ist gegeben durch die Eingabezeichenfolge.

Algorithm getNodeFromString(Graph G, String s): 
     for every node N in G: 
      if N.id == s: 
        return N 

Dies ist natürlich vorausgesetzt, dass jeder Knoten in Graph eine eindeutige Kennung hat.