algorithm - 为什么我们在约翰逊算法中只运行 Dijkstra 算法 V 次？

Question

运行 Bellman-Ford 并重新权衡图形后，我们可以获得正边。但是要找到每对之间的最短路径，这是否意味着我们必须运行 Dijkstra 的 V^2 次？因为对于V个顶点，V选择2 = V(V-1)/2!所以 O(V^2) 时间。为什么我们只运行 Dijkstra 的 V 次？

Answer 1

给定任意两个点，每次我们运行 Bellman-Ford 时，我们都会正确地将我们对最短路径的理解至少扩展一条边。然后停止改进。

最长可能的最短路径访问图中的每个顶点一次。该路径有 V 个顶点和 V-1 个边。因此，一旦我们运行了 V-1 次，我们就必须找到所有可能的最短路径。