适用
含负权边的有向图的单源最短路径问题
不能处理带负权边的无向图和包含权值总和为负值的回路
数据结构
dist[u] :源点到u的最短路径长度
思路
每次更新dist数组，使得 dist[u] 的含义是从源点到u的经过n条边的最短路径长度
递推公式
$Dist^k[u]=min(dist^{k-1}[u],min{dist^{k-1}[j]+Edge[j][u]}),j=0,1,…,n-1,j e u$
负权回路的判断
在求出$dist^{n-1}[]$后，对每条边$<u,k>$判断一下加入这条边会不会使得顶点k的最短路径值再缩短，即判断$dist[u]+w(u,k)<dist[k]$是否成立。
代码
1 int Bellman_ford(int v) { 2 for( int i = 1; i <= N; ++i) 3 dist[i] = INF; 4 dist[v] = 0; 5 for( int k = 1; k < N; ++k) { //经过不超过k条边 6 for( int i = 0;i < edges.size(); ++i) { 7 int s = edges[i].s; 8 int e = edges[i].e; 9 if( dist[s] + edges[i].w < dist[e]) 10 dist[e] = dist[s] + edges[i].w; 11 } 12 } 13 for( int i = 0;i < edges.size(); ++ i) { 14 int s = edges[i].s; 15 int e = edges[i].e; 16 if( dist[s] + edges[i].w < dist[e]) 17 return true; 18 } 19 return false; 20 }