上次我们学习了Dijkstra，其有一个不错的时间复杂度上限：O(n log n)，但其对于负权边的处理会出错啦
一个简单的小例子：
这个图中如果我们发现以3号点为原点，跑一边dijkstra的话
我们先会取2号点进入原点集合，再取一号点。这样得到的dist[2]=3，dist[1]=4
错！
我们很容易发现其实dist[1]=4,dist[2]=2;先取1，再取2。
令人难受接受的是不是我们选取边的方式错了，而是算法本身就有漏洞！
因为上次dijkstra正确性证明时的dist[i]最小，则其则不存在其他店更新i的想法是错的！
这就需要我们寻找一个新的算法
就是bellman了
在这个算法中，我们暴力的把每条边都更新一次，更新|V|-1次，而且如果第|V|次还可以更新的话，就存在负权环了！
百度百科：
描述性证明
首先指出，图的任意一条最短路径既不能包含负权回路，也不会包含正权回路，因此它最多包含|v|-1条边。
其次，从源点s可达的所有顶点如果 存在最短路径，则这些最短路径构成一个以s为根的最短路径树。Bellman-Ford算法的迭代松弛操作，实际上就是按每个点实际的最短路径[虽然我们还不知道，但它一定存在]的层次，逐层生成这棵最短路径树的过程。
注意，每一次遍历，都可以从前一次遍历的基础上，找到此次遍历的部分点的单源最短路径。如：这是第i次遍历，那么，通过数学归纳法，若前面单源最短路径层次为1~（i-1）的点全部已经得到，而单源最短路径层次为i的点，必定可由单源最短路径层次为i-1的点集得到，从而在下一次遍历中充当前一次的点集，如此往复迭代，[v]-1次后，若无负权回路，则我们已经达到了所需的目的--得到每个点的单源最短路径。[注意：这棵树的每一次更新，可以将其中的某一个子树接到另一个点下]
反之，可证，若存在负权回路，第[v]次遍历一定存在更新，因为负权回路的环中，必定存在一个“断点”，可用数学手段证明。
最后，我们在第[v]次更新中若没有新的松弛，则输出结果，若依然存在松弛，则输出‘CAN'T'表示无解。同时，我们还可以通过“断点”找到负权回路。
所以总的时间复杂度为O（n*m），不算优，但可以优化到SPFA，具高效（貌似还是中国人发明的）
另外，运用bellman-Ford算法还可以解决差分约束图的问题
下一篇文章讨论。
代码：
#include<iostream> #include<cstdio> #include<algorithm> #define INF 100000 const int N=500005; struct note{ int u,v,c; }Edge[N]; int dist[N]; using namespace std; int main() { int n,m,s; scanf("%d %d %d",&n,&m,&s); for(int i=1;i<=m;i++) { scanf("%d %d %d",&Edge[i].u,&Edge[i].v,&Edge[i].c); } for(int i=1;i<=n;i++) dist[i]=INF; dist[s]=0; for(int i=1;i<n;i++) { bool flag=1; for(int j=1;j<=m;j++) if(dist[Edge[j].u]+Edge[j].c<dist[Edge[j].v]) dist[Edge[j].v]=dist[Edge[j].u]+Edge[j].c,flag=0; if (flag) break; } cout<<dist[1]; for(int i=2;i<=n;i++) printf(" %d",dist[i]); cout<<endl; } //若有错误请大佬更正