文档介绍：数学建模常用 Matlab/Lingo/c 代码总结系列—— floyd 最短路径分类: Matlab 数学建模 2011-11-16 23:37 186 人阅读评论(0) 收藏举报例9 某公司在六个城市 c1,c2, … c6 中有分公司,从 i ci到 cj 的直接航程票价记在下述矩阵的(I,j) 位置上。(∞表示无直接航路), 请帮助该公司设计一张城市 c1 到其它城市间的票价最便宜的路线图。[plain] view plain copy print ? 1. clc,clear 2. 3. a=zeros(6); 4. 5. a(1,2)=50;a(1,4)=40;a(1,5)=25;a(1,6)=10; 6. 7. a(2,3)=15;a(2,4)=20;a(2,6)=25; 8. 9. a(3,4)=10;a(3,5)=20; 10. 11. a(4,5)=10;a(4,6)=25; 12. 13. a(5,6)=55; 14. 15. a=a+a'; 16. 17. a(find(a==0))=inf; 18. 19. pb(1:length(a))=0;pb(1)=1;index1=1;index2=ones(1,length(a)); 20. 21. d(1:length(a))=inf;d(1)=0;temp=1; 22. 23. while sum(pb)<length(a) 24. 25. tb=find(pb==0); 26. 27. d(tb)=min(d(tb),d(temp)+a(temp,tb)); 28. 29. tmpb=find(d(tb)==min(d(tb))); 30. 31. temp=tb(tmpb(1)); 32. 33. pb(temp)=1; 34. 35. index1=[index1,temp]; 36. 37. temp2=find(d(index1)==d(temp)-a(temp,index1)); 38. 39. index2(temp)=index1(temp2(1)); 40. 41. end 42. 43. d, index1, index2 编写 LINGO 程序如下: [plain] view plain copy print ? 1. model: 2. 3. sets: 4. 5. cities/A,B1,B2,C1,C2,C3,D/; 6. 7. roads(cities,cities)/A B1,A B2,B1 C1,B1C2,B1 C3,B2 C1, 8. 9. B2 C2,B2 C3,C1 D,C2 D,C3 D/:w,x; 10. 11. endsets 12. 13. data: 14. 15. w=2 433123113 4; 16. 17. enddata 18. 19. n=***@size(cities); ! 城市的个数; 20. 21. min=***@sum(roads:w*x); 22. 23. ***@for(cities(i)|i #ne#1 #and# i #ne#n: 24. 25. ***@sum(roads(i,j):x(i,j))=***@sum(roads(j,i):x(j,i))); 26. 27. ***@sum(roads(i,j)|i #eq#1:x(i