Dijkstra 源到目标的有向加权图中的最短路径

Question

在 Dijkstra 的 wiki page 中，我被告知如果目的地已知，我可以在行 13 后终止搜索。我不明白，如何在 13 行后终止搜索？

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

Answer 1

维基百科是错误的，正确的行是 16 在那个算法中。编辑可能破坏了行号或下面的段落。

该段的意思是，如果您只对从顶点 S 到 Q 的最短路径感兴趣，则可以在找到 Q 时安全地退出循环，因为任何其他路径的到达成本都会更高它。伪代码如下

8    for each vertex v in Graph:             // Initialization
9        if v ≠ source:                      // v has not yet been removed from Q (unvisited nodes)
10            dist[v] ← INFINITY             // Unknown distance from source to v
11            prev[v] ← UNDEFINED            // Previous node in optimal path from source
12        add v to Q                          // All nodes initially in Q (unvisited nodes)
13      
14    while Q is not empty:
15        u ← vertex in Q with min dist[u]    // Source node in the first case
16        remove u from Q 
17          
(extra)   if u == destination_point then break loop

当你遇到终点Q时，你可以安全地跳过更新部分，你用最短路径更新任何相邻的顶点 - >你已经找到了你的目的地。要重建路径，只需反向行走矢量 prev 从 destination_point 到源。

更多详细信息和 C++ 示例 here

Answer 2

您需要在第 17 行之后添加一些代码：

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

Dijkstra 源到目标的有向加权图中的最短路径

Dijkstra source to destination shortest path in directed, weighted graph

algorithm

graph

pseudocode

dijkstra

shortest-path