这时候dis[2]和dis[5]的值变小了，如果再做一轮松弛操作的话，之前不成功的松弛这时候也能也就可以起作用了。
换句话说，第一轮松弛后得到的是从1号出发“只能经过1条边”到达其余各点的最短路，第二轮松弛后得到的是“只能经过2条边”到达其余各点的最短路，如果进行第k轮松弛得到的就是“只能经过k条边”到达其余各点的最短路。
那么到底需要进行多少轮呢？答案是n-1轮。因为在一个含有n个顶点的图中，任意两点间的最短路最多包含n-1条边。也就解释了代码的第一行，是在进行n-1轮松弛。
完整代码：
for(int i = 1; i <= n; i++) dis[i] = INF; dis[1] = 0; //初始化dis数组，只有1号的距离为0 for(int k = 1; k <= n-1; k++) //进行n-1轮松弛 for(int i = 1; i <= m; i++) //枚举每一条边 if(dis[v[i]] > dis[u[i]] + w[i]) //尝试进行松弛 dis[v[i]] = dis[u[i]] + w[i];此外，Bellman-Ford算法还可以检测一个图是否含有负权回路。如果在进行了n-1次松弛之后，仍然存在某个dis[v[i]] > dis[u[i]] + w[i]的情况，还可以继续成功松弛，那么必然存在回路了（因为正常来讲最短路径包含的边最多只会有n-1条）。
判断负权回路也即在上面那段代码之后加上一行：
for(int i = 1; i <= m; i++) if(dis[v[i]] > dis[u[i]] + w[i]) flag = 1;Bellman-Ford算法的时间复杂度是O(nm)，貌似比Dijkstra还高。事实上还可以进行优化，比如可以加一个bool变量check用来标记数组dis在本轮松弛中是否发生了变化，如果没有，就可以提前挑出循环。因为是“最多”达到n-1轮，实际情况下经常是早就已经达到最短，没法继续成功松弛了。
for(int k = 1; k <= n-1; k++) //进行n-1轮松弛 { bool check = 0; for(int i = 1; i <= m; i++) //枚举每一条边 if(dis[v[i]] > dis[u[i]] + w[i]) //尝试进行松弛 { dis[v[i]] = dis[u[i]] + w[i]; check = 1; } if(check == 0) break; }另外一种优化是：每次仅对最短路估计值发生了变化的结点的所有出边进行松弛操作。因为在上面的算法中，每实施一次松弛操作后，就会有一些顶点已经求得最短路之后便不会再改变了（由估计值变为确定值），既然都已经不受后续松弛操作的影响了却还是每次都要判断是否需要松弛，就浪费了时间。
可以用队列来维护dis发生了变化的那些结点。具体操作是：
初始时将源点加入队列。
每次选取队首结点u，对u的所有出边进行松弛。假设有一条边u->v松弛成功了，那就把v加入队列。然而，同一个结点同时在队列中出现多次是毫无意义的（可以用一个bool数组来判哪些结点在队列中）。所以刚提到的操作其实是，如果v不在当前队列中，才把它加入队列。
对u的所有出边松弛完毕后，u出队。接下来不断的取出新的队首做第2步操作，直到队列为空。
一个例子：
用数组dis来存放1号结点到各点的最短路。初始时dis[1]为0。接下来将1号结点入队。
现在看1号的所有出边，对于1->2，比较dis[2]和dis[1]+e[1][2]的大小，发现松弛成功，dis[2]从INF变为2。并且2不在队列中，所以2号结点入队。同理，5号结点也松弛成功，入队。
1号结点处理完毕，此时将1号出队，接着对队首也就是2号结点进行同样的处理。在处理2->5这条边的时候，虽然松弛成功，dis[5]从10更新为9了，但5号顶点已经在队列中，所以5号不能再次入队。
处理完2号之后就长这样：