python-3.x - 贝尔曼-福特 :- Why are there N-1 iterations for calculating mindistance?

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

上述函数是Bellman-Ford算法实现的一部分。我的问题是，如何确定在 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 条边，那么至少有一个顶点被使用了两次，所以这样的路径将包含一个循环。