如何找到最短路徑在相等加權圖

Question

我有看起來像這樣的曲線圖： 所有節點之間的邊緣具有距離= 1

 F 
     | 
     E 
     | 
A-B-C-D 
|  | 
G  O 
|  | 
H  P 
|  | 
I  Q 
|  | 
J  R 
|  | 
K-L-M-N 

我必須找到從A節點的最短路徑到Q. 我使用如下（從維基百科借來的）算法：

1 function Dijkstra(Graph, source): 
2 
3  create vertex set Q 
4 
5  for each vertex v in Graph:    // Initialization 
6   dist[v] ← INFINITY     // Unknown distance from source to v 
7   prev[v] ← UNDEFINED     // Previous node in optimal path from source 
8   add v to Q       // All nodes initially in Q (unvisited nodes) 
9 
10  dist[source] ← 0      // Distance from source to source 
11  
12  while Q is not empty: 
13   u ← vertex in Q with min dist[u] // Source node will be selected first 
14   remove u from Q 
15   
16   for each neighbor v of u:   // where v is still in Q. 
17    alt ← dist[u] + length(u, v) 
18    if alt < dist[v]:    // A shorter path to v has been found 
19     dist[v] ← alt 
20     prev[v] ← u 
21 
22  return dist[], prev[] 

當我使用djikstra的算法中存在的主要問題是，我沒能獲得的最短路徑從源到目的地穿越。 算法遍歷不在最短路徑中的節點，找到最短路徑。

E.g if i traverse from A->Q i traverse through other nodes like(G->H->I..) 
But the path from G->H->I does not lead to the destination. 
But the path from A->B->C... leads to the shortest path. 

我該如何回溯正確的路徑？

Answer 1

這就是在djikstra算法的分組陣列是

你知道目的地是Q，所以上一頁[Q]是節點的最優路徑Q（在這種情況下是P）

前右

prev [P]是O，prev [O]是D，依此類推，直到你到達A，這是路徑的起點。