我有一个如下图：节点之间的所有边都有距离= 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.
我如何回溯正确的路径？
1 回答
这就是djikstra算法中的prev数组的用途
你知道目的地是Q，所以prev [Q]是最佳路径中Q之前的节点（在这种情况下是P）
prev [P]是O，prev [O]是D，依此类推，直到你到达A这是路径的起源 .