Bellman-Ford算法能解决负权边的图，就是说能够来判断存在负环。
先来看一下核心代码：
最外层一共循环了n-1次，内循环循环了m次，
内循环的意思就是：通过每一条边来松弛每两个顶点之间的距离。
外循环n-1次的原因：因为在一个包含n个顶点的图中，任意两点之间的最短路最多包含n-1条边。
有些特别爱思考的同学又会发出一个疑问：真的最多只能包含n-1条边？最短路径中不可能包含回路么？
答案是：不可能！最短路径肯定是一个不包含回路的简单路径。回路分为正权回路（即回路权值之和为正）和负权回路（即回路权值之和为负）。分别讨论一下为什么这两种回路都不可能有。如果最短路径中包含正权回路，那么去掉这个回路，一定可以得到更短的路径。如果最短路径中包含负权回路，那么肯定没有最短路径，因为每多走一次负权回路就可以得到更短的路径。因此，最短路径肯定是一个不包含回路的简单路径，即最多包含n-1条边，所以进行n-1轮松弛就可以了。
if(flag)//判断是否存在负环，也就是说在进行N-1轮松弛后， 仍然可以继续松弛成功，那么此图必然存在负权回路。在之前证明中已经讨论过，如果一个图没有负权回路，那么最短路径所包含的边最多为N-1条，即进行N-1轮松弛之后最短路不会再发生变化。如果在N-1轮松弛之后最短路仍然会发生变化，则该图必然存在负权回路。
每次仅对最短路程发生变化了的点的相邻边执行松弛操作。但是如何知道当前哪些点的最短路程发生了什么变化呢？这里可以用一个队列来维护这些点。
每次选取队首顶点u（随意命名的），对顶点u的所有出边进行松弛操作。例如有一条u->v的边，如果通过u->v这条边是的源点到顶点v的最短路程变短（dis[u] + edge[u][v] < dis[v]）且顶点v不在当前队列中，就将顶点v放入队尾。需要注意的是，同一个顶点同事在队列中出现多次是毫无意义的，所以需要一个标记数组进行判重（判断哪些点已经在队列中）。在对顶点u的所有出边松弛完毕之后，就将顶点u出队。接下来不断从队列中取出队首顶点再进行如上操作，直到队列空为止。
本文转自网络文章，转载此文章仅为分享知识，如有侵权，请联系博主进行删除。