algorithm - 是否存在真正的单对最短路径算法？

Question

我今天遇到这个术语“单对最短路径问题”。我想知道加权图是否存在单对最短路径算法。我的推理可能有缺陷，但我想如果你想找到 A 和 Z 之间的最短路径，你绝对必须知道从 A 到 B、C、D、... Y 的最短路径。

如果你不知道后者，你就不能确定你的路径实际上是最短的。因此对我而言，任何最短路径算法都必须计算从 A 到图中每个其他顶点的最短路径，以便获得从 A 到 Z 的最短路径。

这是正确的吗？

PS:如果是，是否有任何研究论文可以恰本地证明这一点？

Answer 1

对于非负加权边图问题，Dijkstra 本身解决了给定问题。

引用自维基

The algorithm exists in many variants; Dijkstra's original variant found the shortest path between two nodes, but a more common variant fixes a single node as the "source" node and finds shortest paths from the source to all other nodes in the graph, producing a shortest-path tree.

考虑以下来自 wiki 的伪代码:

 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]    // Node with the least distance 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[]

随着 while (12) 的每次新迭代，第一步选择与剩余集合 Q 距离最短的顶点 u (13) 然后从 Q 中移除该顶点 (14) 通知已实现到 u 的最短距离。如果 u 是您的目的地，那么您可以停止而不考虑进一步的边缘。

请注意，所有顶点都已使用，但未使用所有边，并且尚未找到到所有顶点的最短路径。