是否存在真正的单对最短路径算法？
Is there a true single-pair shortest path algorithm?
我今天看到这个词"single-pair shortest path problem"。我想知道加权图是否存在单对最短路径算法。我的推理可能有缺陷，但我想如果你想找到 A 和 Z 之间的最短路径，你绝对必须知道从 A 到 B、C、D、... Y 的最短路径。
如果你不知道后者，你就不能确定你的路径实际上是最短的。因此对我来说，任何最短路径算法都必须计算从 A 到图中每个其他顶点的最短路径，以便获得从 A 到 Z 的最短路径。
这是正确的吗？
PS：如果是，有没有研究论文能正确证明这一点？
对于非负加权边图问题，Dijkstra 本身解决了给定问题。
引自 wiki
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 (13) 距离最短的顶点 u，然后选择该顶点从 Q (14) 中删除，通知已达到到 u 的最短距离。如果 u 是你的目的地，那么你可以停止而不考虑进一步的边缘。
请注意，已使用所有顶点但未使用所有边，并且尚未找到到所有顶点的最短路径。
引用 CLRS，第 3 版，第 24 章：
Single-pair shortest-path problem: Find a shortest path from u to v for given vertices u and v. If we solve the single-source problem with source vertex u, we solve this problem also. Moreover, all known algorithms for this problem have the same worst-case asymptotic running time as the best single-source algorithms
我今天看到这个词"single-pair shortest path problem"。我想知道加权图是否存在单对最短路径算法。我的推理可能有缺陷，但我想如果你想找到 A 和 Z 之间的最短路径，你绝对必须知道从 A 到 B、C、D、... Y 的最短路径。
如果你不知道后者，你就不能确定你的路径实际上是最短的。因此对我来说，任何最短路径算法都必须计算从 A 到图中每个其他顶点的最短路径，以便获得从 A 到 Z 的最短路径。
这是正确的吗？
PS：如果是，有没有研究论文能正确证明这一点？
对于非负加权边图问题，Dijkstra 本身解决了给定问题。
引自 wiki
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 (13) 距离最短的顶点 u，然后选择该顶点从 Q (14) 中删除，通知已达到到 u 的最短距离。如果 u 是你的目的地，那么你可以停止而不考虑进一步的边缘。
请注意，已使用所有顶点但未使用所有边，并且尚未找到到所有顶点的最短路径。
引用 CLRS，第 3 版，第 24 章：
Single-pair shortest-path problem: Find a shortest path from u to v for given vertices u and v. If we solve the single-source problem with source vertex u, we solve this problem also. Moreover, all known algorithms for this problem have the same worst-case asymptotic running time as the best single-source algorithms