Bellman.doc

《Bellman.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、结束点开始点图：最短路径算法模型图//Bellman-Ford经典算法的实现#include#include#defineM999999typedefstructedge//建立边信息{intu,v;}edge;edgee[10];intg[6][6]={{M,M,M,M,M,M},//初始化一幅图{M,M,5,-4,8,M},{M,-2,M,M,M,M},{M,M,7,M,M,2},{M,M,-3,9,M,M},{M,6,M,M,7,M}};intmain()//主程序{intk=0,

2、i=0,j=0;intl1,l2;intShortline=0;//最短路径intd[5];//该点到开始点的距离intex=0;//测试算法是否可以提前结束intnNum=5;//图的顶点数inteNum=10;//图的边数//建立边信息，结果保存在e[]中for(i=0;i<7;i++){for(j=0;j<7;j++){if(g[i][j]!=0&&g[i][j]!=M){e[k].u=i;e[k].v=j;k++;}}}//Bellman-Ford算法开始for(l1=1;l1

3、每个结点到开始点的距离都是MAXd[l1]=M;d[5]=0;//设开始点的最短距离为0ex=1;for(l1=1;l1d[e[l2].u]+g[e[l2].u][e[l2].v])//按每个节点顺序对每条边进行一次松弛操作{d[e[l2].v]

4、=d[e[l2].u]+g[e[l2].u][e[l2].v];ex=1;printf("thed[%d]'sweightis:%d",e[l2].v,d[e[l2].v]);}}Shortline=d[1];//把目的节点的最短距离值付给shortlineprintf("Theshortestline'weightis:%d",Shortline);//打印出从开始节点到目标节点的最短距离getchar();return0;}表经典Bellman-Ford算法执行过程WijD(t)(v1,vj)V1V2V3V4

5、V5第一次第二次第三次第四次V1V2V3V4V5图：程序的输出结果//Bellman-Ford算法的改进——YEN氏改进的测试程序//建立边信息，结果保存在e[]中，建立顺序遵照Yen氏改进相关要求for(i=0;i<6;i++){for(j=0;j<6;j++){if(g[i][j]!=0&&g[i][j]!=M&&i=0;i--){for(j=5;j>=0;j--){if(g[i][j]!=0&&g[i][j]!=M&&i>j){e[k].u=

6、i;e[k].v=j;k++;}}}//bellman-ford算法开始for(l1=1;l1d[e[

7、l2].u]+g[e[l2].u][e[l2].v])//按Yen氏改进顺序对每条边进行一次松弛操作{d[e[l2].v]=d[e[l2].u]+g[e[l2].u][e[l2].v];ex=1;printf("thed[%d]'sweightis:%d",e[l2].v,d[e[l2].v]);}}Shortline=d[1];//把目的节点的最短距离值付给shortlineprintf("Theshortestline'weightis:%d",Shortline);//打印出从开始节点到目标节点的最短距离g

8、etchar();return0;}表Bellman-FordYen氏改进算法的执行过程WijD(t)(v1,vj)V1V2V3V4V5第一次第二次第三次第四次V1V2V3V4V5图：Bellman-FordYen氏改进算法的输出结果//Bellman-Ford算法钱氏改进的测试程序//建