如何在等权图中寻找最短路径

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算法中的prev数组的用途

您知道目的地是Q，所以prevQ是最优路径中Q之前的节点(在本例中是P)

prevP是O，prevO是D，依此类推，直到到达路径的原点A为止。