此算法是解决单源最短路径的一种算法，Dijkstra算法虽然也是，但是有自己的局限性，就是不能存在负权边。这是为什么呢？因为Dijkstra实际上是贪心法，在每一步都选择最优解，即每次都选择最近的一个点，但是负权边的加入会打破这一性质，就使得Dijkstra算法失效了。为了解决这一问题，可以使用这里的Bellman-Ford算法，对每条边进行松弛。
#include<iostream>using namespace std;int main(){int dis[10], back[10], u[10], v[10], w[10];int n, m, check, flag;cin >> n >> m;for(int i = 1; i <= m; i++) cin >> u[i] >> v[i] >> w[i];for(int i = 1; i <= n; i++) dis[i] = 99999;dis[1] = 0;//Bellman-Ford/*dis[v[i]] > dis[u[i]] + w[i]表示加入边u->v后,1到v[i]的最短距离能否通过1->u[i]->v[i]变得更小,如果可以则松弛将m条边松弛一遍,是加入一条边的情况;松弛k遍即加入k条边一个n个顶点的图,最短路径最多只有n - 1条边如果存在负权回路,则第n次松弛的时候dis数组仍然会有变化 */for(int k = 1; k <= n - 1; k++){//backupfor(int i = 1; i <= n; i++) back[i] = dis[i];//slackfor(int i = 1; i <= m; i++)if(dis[v[i]] > dis[u[i]] + w[i])dis[v[i]] = dis[u[i]] + w[i];//checkcheck = 0;for(int i = 1; i <= n; i++)if(back[i] != dis[i]){check = 1;break;}if(check == 0) break;}//check negative weighted edgeflag = 0;for(int i = 1; i <= m; i++)if(dis[v[i]] > dis[u[i]] + w[i])flag = 1;if(flag == 1) cout << "The graph has nagative weighted circle" << endl;else{for(int i = 1; i <= n; i++)cout << dis[i] << " ";}return 0;
}/*
input:
5 5
2 3 2
1 2 -3
1 5 5
4 5 2
3 4 3output:
0 -3 -1 2 4
*/
上面的代码中已经是Bellman-Ford的一种优化算法，当进行完一轮松弛操作以后，如果所有点的最短距离都没有发生变化，那么就没有必要再次进行松弛了，可以及时跳出循环。还有另一种优化方式，就是用一个队列来存储顶点，对队首顶点的所有相连的边进行松弛，再将每条边的另一个顶点入队，直到队列为空。此时dis数组不再发生变化，因为没有顶点入队导致队列为空。需要注意，同一顶点同时在队列中多次出现是没有意义的，只需出现一次即可。可以申请一个数组用于记录某个顶点是否在队列之中。