Bellman.doc

Bellman.doc

ID:48878279

大小:360.00 KB

页数:9页

时间:2020-02-04

Bellman.doc_第1页
Bellman.doc_第2页
Bellman.doc_第3页
Bellman.doc_第4页
Bellman.doc_第5页
资源描述:

《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算法钱氏改进的测试程序//建

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。
相关文章
更多
相关标签