Bellman-Ford：- 为什么需要 N-1 次迭代来计算介距？

Question

def calculateShortestPath(self,vertexList,edgeList,startVertex):
    startVertex.minDistance=0

    for i in range(0,len(vertexList)-1):#N-1 ITERATION
        for edge in edgeList:
            #RELAXATION PROCESS
            u=edge.startVertex
            v=edge.targetVertex
            newDistance=u.minDistance+edge.weight
            if newDistance<v.minDistance:
                v.minDistance=newDistance
                v.predecessor=u
    for edge in edgeList:# FINAL ITERATION TO DETECT NEGATIVE CYCLES
        if self.hasCycle(edge):
            print("NEGATIVE CYCLE DETECTED")
            self.HAS_CYCLE=True
            return

上述函数是贝尔曼-福特算法实现的一部分。我的问题是，如何确定经过 N-1 次迭代后，已经计算出最小距离？在 Dijkstra 的情况下，据了解，一旦优先级队列变空，所有最短路径都已创建，但我无法理解此处 N-1 背后的推理。

N-Length of the Vertex List.
Vertex List-contains the different vertex.
EdgeList-List of the different Edges.

由于我是从教程视频中阅读的，因此实施可能是错误的。感谢您的帮助

Answer 1

外循环执行N-1次，因为最短路径不能包含更多边，否则最短路径将包含循环，这是可以避免的。

次要：如果有 N 个顶点和 N 个边，则至少有 1 个顶点被使用两次，因此这样的路径将包含循环。

Answer 2

该算法与 Djkstra 不同，不是贪婪的，而是动态的。在循环的第一次迭代中，它在两个顶点之间构建一条可能的路径，然后在每次迭代时它都会将路径改进至少一条边。由于最短路径可以使用最多 n-1 条边，因此循环迭代会继续下去以找到最短路径。

对于负循环，算法在第 n 次迭代时再检查一次以查看是否存在边，以减少具有 n-1 条边的最短路径的权重。如果是，则该边必须为负，因为具有所有正边的最短路径应由 n-1 而不是 n 边组成。