会计学Bellman-Ford算法(suànfǎ)思想distk[u]的计算(jìsuàn)4算法(suànfǎ)实现for(k=2;k<vexnum;k++)//从dist1[u]递推出dist2[u],…,distn-1[u]{for(u=0;u<vexnum;u++)//修改(xiūgǎi)每个顶点的dist[u]和path[u]{if(u!=v){for(i=0;i<vexnum;i++)//考虑其他每个顶点{if(Edge[i][u]<MAX&&dist[u]>dist[i]+Edge[i][u]){dist[u]=dist[i]+Edge[i][u];path[u]=i;}}}}}}Dijkstra算法(suànfǎ)与Bellman算法(suànfǎ)的区别如果(rúguǒ)存在从源点可达的负权值回路，则最短路径不存在，因为可以重复走这个回路，使得路径无穷小。在Bellman算法中判断是否存在从源点可达的负权值回路的方法：算法(suànfǎ)复杂度分析Bellman-Ford算法(suànfǎ)思想的另一种理解#defineMAX999999#defineEDGE_MAX100//边数最大值#defineVER_MAX50//顶点个数最大值structEdge{intu,v,w;//边：起点、终点、权值};Edgeedges[EDGE_MAX];//存储所有的边intm;//实际边的个数intn;//顶点个数/*dist为源点v0到各顶点的最短距离,如果(rúguǒ)初始为v0到各顶点直接边的长度,则算法中的循环要执行n-2次，如果(rúguǒ)初始为MAX，则循环要执行n-1次，第一次求得的dist就是v0到各顶点直接边的长度*/intdist[VER_MAX]={MAX};//假定边的数组、边的个数这些信息已经读进来了boolbellman_ford()//bellman-ford算法{inti,k,t;for(i=1;i<n;i++){/*假设第k条边的起点是u,终点是v,以下循环考虑第k条边是否会使得源点v0到v的最短距离缩短,即判断dist[edges[k].u]+edges[k].w<dist[edges[k].v]是否成立*/for(k=0;k<m;k++){t=dist[edges[k].u]+edges[k].w;if(dist[edges[k].u]!=mx&&t<dist[edges[k].v]){dist[edges[k].v]=t;}}}/*以下是检查，若还有更新则说明存在无限循环的负值(fùzhí)回路*/for(k=0;k<m;k++){if(dist[edges[k].u]!=MAX&&dist[edges[k].u]+edges[k].w<dist[edges[k].v]){returnfalse;}}returntrue;}Bellman-Ford算法(suànfǎ)改进例题(lìtí)