No.6.3 最短路径之Bellman-Ford算法--解决负权边

本文主要是介绍No.6.3 最短路径之Bellman-Ford算法--解决负权边，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

一、无论Floyd还是Dijkstra，算法的假设前提就是，没有负权边。

但是Bellman-Ford算法可以：

　　if( dis[v[i]] > dis[u[i]] + w[i])

　　　　dis[v[i]] = dis[u[i]] + w[i];

　　u[i], v[i], w[i] 分别记录一条边的起点，终点，边长；dis[x] 表示源点 1 到 顶点 x 的最短距离；

　　那么算法的意思就是：如果通过顶点 u[i] 使得 源点 1 到 顶点 v[i] 的距离变短，那么执行Dijkstra的“松弛“操作！

过程：

　　1.先按照给定边的顺序松弛，这时表示的是源点 1 ，只能经过一条边时，到达其他各点的最短路径；

　　2.重复松弛，这时表示的是源点 1 ，经过 2<= k <= n-2 条边时（n个节点之间最多n-1条边，仅需松弛循环n-2次），可到达其他各点的最短路径；

　　3.k>=n的可能性（回路）：如果是正权回路，那么越走越远；如果是负权回路，则没有最短路径。所以不可能有最短路径中不可能有回路；

二、code

int main(){
　　int i,j,n,m;
　　int dis[10];
　　int inf=999999;
　　int u[10],v[10],w[10];

　　scanf("%d %d",&n,&m); //n=点数，m=边数

　　for(i=1;i<=m;i++){
　　　　scanf("%d %d %d",&u[i],&v[i],&w[i]);
　　}

　　for(i=1;i<=n;i++)
　　　　dis[i]=inf;
　　dis[1]=0;

　　for(i=1;i<=n-1;i++){　　　  //Bellman-Ford 算法核心
　　　　for(j=1;j<=m;j++){ 　　//松弛的对象是边，不是点！
　　　　　　if(dis[v[j]] > dis[u[j]] + w[j])
　　　　　　　　dis[v[j]] = dis[u[j]] + w[j];
　　　　}
　　}

　　//如果n-1轮松弛之后，最短路径依然会发生变化，说明该图存在负权回路！
　　for(i=1;i<=m;i++)
　　　　if(dis[v[i]] > dis[u[i]] + w[i])
　　　　　　printf("图中存在负权回路");

　　for(i=1;i<=n;i++)
　　　　printf("%d\t",dis[i]);

　　getchar();getchar();return 0;
}

算法的时间复杂度为O(NM)，对于稀疏图来说，比Dijkstra要高效的多！

这篇关于No.6.3 最短路径之Bellman-Ford算法--解决负权边的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！