Matlab代码-佛洛依德最短路径

1、数学建模常用Matlab/Lingo/c代码总结系列floyd最短路径分类：Matlab数学建模 2011-11-16 23:37 186 人阅读 评论(0)收藏 举报例9 某公司在六个城市c1,c2, -c6中有分公司，从 ici到cj的直接航程票价记在下述矩阵的(I,j)位置上。(8表示无直接航路)，请帮助该公司设计一张城市c1到其它城市间的票价最便宜的路线图。500040251050 0 15 20 x 25 X)501020x4020100102525x20100551025x25550F 用矩阵卜为M点个数)存放各边权的Z接花苫.行勺量冲仍曲山、访赤勺、 d分别用来存放尸标号信息、标

2、号顶点顺序、标号顶点索引,最短通路的值其中分 量I L 当第撷点已标号 pb(i)- <；0当第i顶点未标号index. (/)存放始点到第i点最短通路中第i顶点前一项点的序号： d(i)存放由始点到第I点最短通路的值，|求第一个城市到其它城市的最短路径的、.1浏北程序如下：plain view plaincopyprint?1. clc,clear2.2. a=zeros(6);4.3. a(1,2)=50;a(1,4)=40;a(1,5)=25;a(1,6)=10;6.4. a(2,3)=15;a(2,4)=20;a(2,6)=25;8.5. a(3,4)=10;a(3,5)=20;

3、10.6. a(4,5)=10;a(4,6)=25;12.13. a(5,6)=55;14.15. a=a+a'16.16. a (find(a=0)=inf;18.17. pb(1:length(a)=0;pb(1)=1;index1=1;index2=ones(1,length(a);20.18. d (1:length(a)=inf;d(1)=0;temp=1;22.19. while sum(pb)<length(a)24.20. tb=find(pb=0);26.21. d(tb)=min(d(tb),d(temp)+a(temp,tb);28.22. tmpb=fin

4、d(d(tb)=min(d(tb);30.23. temp=tb(tmpb(1);32.24. pb(temp)=1;34.25. index1=index1,temp;36.26. temp2=find(d(index1)=d(temp)-a(temp,index1);38.27. index2(temp)=index1(temp2(1);40.28. end42.29. d, index1, index2例10在图3中*用点表示城市，现有共7个城市坦点 点之间的连线在示城市间有道路相连。连线旁的数字表示道路的长度。现计划从城市 到城市。铺设一条天然气管道，请设计出最小价格管道铺设方案，阁3

5、 ，个城市间的连线图编写LINGO程序如下：plain view plaincopyprint?1. model:2.2. sets:4.3. cities/A,B1,B2,C1,C2,C3,D/;6.4. roads(cities,cities)/A B1,A B2,B1 C1,B1C2,B1 C3,B2 C1,8.5. B2 C2,B2 C3,C1 D,C2 D,C3 D/:w,x;10.6. endsets12.7. data:14.8. w=2 4 3 3 1 2 3 1 1 3 4;16.9. enddata18.10. n=size(cities); !城市的个数； 20.21.

6、m in=sum(roads:w*x);22.22. for(cities(i)|i #ne#1 #and# i #ne#n:24.23. sum(roads(i,j):x(i,j)=sum(roads(j,i):x(j,i);26.24. sum(roads(i,j)|i #eq#1:x(i,j)=1;28.25. sum(roads(i,j)|j #eq#n:x(i,j)=1;30.26. end例II （无向图的最短路问题）求图4中明到上的最短谿为分折 例10处理的问题属于有向图的最短路问题，本例是处理无向图的最短路& 题,在处理方式上与有向图的最短路问题有一些差削，这里选择赋权

7、邻接矩阵的方法& 写LING。程序。屈4无向图的最短路问我 缩写LINGO程序如下：plain view plaincopyprint?1. model:2.3. sets:4.4. cities/1.11/;6.5. roads(cities,cities):w,x;8.6. endsets10.7. data:12.8. w=0;14.9. enddata16.10. calc:18.11. w(1,2)=2;w(1,3)=8;w(1,4)=1;20.12. w(2,3)=6;w(2,5)=1;22.13. w(3,4)=7;w(3,5)=5;w(3,6)=1;w(3,7)=2;2

8、4.14. w(4,7)=9;26.15. w(5,6)=3;w(5,8)=2;w(5,9)=9;28.16. w(6,7)=4;w(6,9)=6;30.17. w(7,9)=3;w(7,10)=1;32.18. w(8,9)=7;w(8,11)=9;34.19. w(9,10)=1;w(9,11)=2;w(10,11)=4;36.20. for(roads(i,j):w(i,j)=w(i,j)+w(j,i);38.21. for(roads(i,j):w(i,j)=if(w(i,j) #eq# 0,1000,w(i,j);40.22. endcalc42.23. n=size(cities)

9、; !城市的个数；44.24. min=sum(roads:w*x);46.25. for(cities(i)|i #ne#1 #and# i #ne#48.26. n :sum(cities(j):x(i,j)=sum(cities(j):x(j,i);50.27. sum(cities(j):x(1,j)=1;52.28. sum(cities(j):x(j,1)=0; !不能回到顶点 1;54.29. sum(cities(j):x(j,n)=1;56.30. for(roads:bin(x);58.31. end60.61.例12用Floyd算法求解例9。矩阵path用来存放每对顶点之

10、间最短路径上所经过的顶点的序号。Floyd算法的Matlab程序如下：plain view plaincopyprint?1. clear;clc;2.2. n=6; a=zeros(n);4.3. a(1,2)=50;a(1,4)=40;a(1,5)=25;a(1,6)=10;6.4. a(2,3)=15;a(2,4)=20;a(2,6)=25;a(3,4)=10;a(3,5)=20;8.5. a(4,5)=10;a(4,6)=25; a(5,6)=55;10.6. a=a+a' M=max(max(a)*nA2; %M为充分大的正实数12.7. a=a+(a=0)-eye(n)*M

11、;14.8. path=zeros(n);16.9. for k=1:n18.10. for i=1:n20.11. for j=1:n22.12. if a(i,j)>a(i,k)+a(k,j)24.13. a(i,j)=a(i,k)+a(k,j);26.14. path(i,j)=k;28.15. end30.16. end32.17. end34.18. end36.37. a, path我们使用LINGO9.0编写的FLOYD算法如下：plain view plaincopyprint?1. model:2.2. sets: nodes/c1.c6/;4.3. link(node

12、s,nodes):w,path; !path标志最短路径上走过的顶点6.4. endsets8.5. data:10.6. path=0;12.7. w=0;14.8. text(mydata1.txt)=writefor(nodes(i):writefor(nodes(j):16.9. format(w(i,j),' 10.0f),newline(1);18.10. text(mydata1.txt)=write(newline(1);20.11. text(mydata1.txt)=writefor(nodes(i):writefor(nodes(j):22.12. format(path(i,j),' 10.0f),newline(1);24.13. enddata26.14. calc:28.15. w(1,2)=50;w(1,4)=40;w(1,5)=25;w(1,6)=10;30.16. w(2,3)=15;w(2,4)=20;w(2,6)=25;32.17. w(3,4)=10;w(3,5)=20;34.18. w(4,5)=10;w(4,6)=25;w(5,6)=55;36.19. for(link(i,j):w(i,j)=w(i,j)+w(j,i);38.20. for(link(i,j) |i