在运行Bellman-Ford并重新加权图之后，我们可以获得积极的优势。但要找到每一对之间的最短路径，这是不是意味着我们必须运行Dijkstra的V ^ 2次？因为对于V顶点，V选择2 = V（V-1）/ 2！所以O（V ^ 2）时间。为什么我们只运行Dijkstra的V次？
鉴于任何两点，每次我们运行Bellman-Ford时，我们都会通过至少一个边缘正确地扩展我们对最短路径的理解。然后停止改进。
最长的最短路径访问图中的每个顶点一次。该路径有V顶点和V-1边缘。因此，一旦我们运行V-1次，我们必须找到所有可能的最短路径。