是否有真正的单对最短路径算法？

Question

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

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

这样对吗？

PS：如果是，是否有任何研究论文可以正确证明这一点？

Answer 1

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

来自维基的引用

该算法存在多种变体；Dijkstra 的原始变体找到了两个节点之间的最短路径，但更常见的变体将单个节点固定为“源”节点，并找到从源到图中所有其他节点的最短路径，生成最短路径树。

考虑以下来自维基的伪代码：

 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）的每次新迭代，首先选择u与剩余集合Q（13）距离最短的顶点，然后从Q（14）中删除该顶点，通知u已达到最短距离。如果u是您的目的地，那么您可以停下来而无需考虑进一步的边缘。

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

Answer 2

引用 CLRS，第 3 版，第 24 章：

单对最短路径问题：对于给定的顶点 u 和 v，找到从 u 到 v 的最短路径。如果我们解决具有源顶点 u 的单源问题，我们也解决了这个问题。此外，该问题的所有已知算法都具有与最佳单源算法相同的最坏情况渐近运行时间