matlablingo程序代码1最短距离.docx
matlablingo程序代码1最短距离例 9 某公司在六个城市 c1, c2, c6 中有分公司，从 i ci到cj的直接航程票价记在下述矩阵的(I,j)位置上。，请帮助该公司设计一张城市c1到其它城市间的票价最便宜的路线图。 clc,clear a=zeros(6); a(1,2)=50;a(1,4)=40;a(1,5)=25;a(1,6)=10; a(2,3)=15;a(2,4)=20;a(2,6)=25; a(3,4)=10;a(3,5)=20; a(4,5)=10;a(4,6)=25; a(5,6)=55; a=a+a' a(find(a=0)=inf; pb(1:length(a)=0;pb(1)=1;index1=1;index2=ones(1,length(a); d(1:length(a)=inf;d(1)=0;temp=1; while sum(pb)<length(a) tb=find(pb=0); d(tb)=min(d(tb),d(temp)+a(temp,tb); tmpb=find(d(tb)=min(d(tb); temp=tb(tmpb(1); pb(temp)=1; index1=index1,temp; temp2=find(d(index1)=d(temp)-a(temp,index1); index2(temp)=index1(temp2(1); end d, index1, index2 编写 LINGO 程序如下： model: sets: cities/A,B1,B2,C1,C2,C3,D/; roads(cities,cities)/A B1,A B2,B1 C1,B1 C2,B1 C3,B2 C1, B2 C2,B2 C3,C1 D,C2 D,C3 D/:w,x; endsets data: w=2 4 3 3 1 2 3 1 1 3 4; enddata n=size(cities); !城市的个数; min=sum(roads:w*x); for(cities(i)|i #ne#1 #and# i #ne#n: sum(roads(i,j):x(i,j)=sum(roads(j,i):x(j,i); sum(roads(i,j)|i #eq#1:x(i,j)=1; sum(roads(i,j)|j #eq#n:x(i,j)=1; end model: sets: cities/1.11/; roads(cities,cities):w,x; endsets data: w=0; enddata calc: w(1,2)=2;w(1,3)=8;w(1,4)=1; w(2,3)=6;w(2,5)=1; w(3,4)=7;w(3,5)=5;w(3,6)=1;w(3,7)=2; w(4,7)=9; w(5,6)=3;w(5,8)=2;w(5,9)=9; w(6,7)=4;w(6,9)=6; w(7,9)=3;w(7,10)=1; w(8,9)=7;w(8,11)=9; w(9,10)=1;w(9,11)=2;w(10,11)=4; for(roads(i,j):w(i,j)=w(i,j)+w(j,i); for(roads(i,j):w(i,j)=if(w(i,j) #eq# 0, 1000,w(i,j); endcalc n=size(cities); !城市的个数; min=sum(roads:w*x); for(cities(i)|i #ne#1 #and# i #ne# n:sum(cities(j):x(i,j)=sum(cities(j):x(j,i); sum(cities(j):x(1,j)=1; sum(cities(j):x(j,1)=0; !不能回到顶点1; sum(cities(j):x(j,n)=1; for(roads:bin(x); end 例12 用Floyd算法求解例9。 矩阵path用来存放每对顶点之间最短路径上所经过的顶点的序号。Floyd算法的 Matlab程序如下： clear;clc; n=6; a=zeros(n); a(1,2)=50;a(1,4)=40;a(1,5)=25;a(1,6)=10; a(2,3)=15;a(2,4)=20;a(2,6)=25; a(3,4)=10;a(3,5)=20; a(4,5)=10;a(4,6)=25; a(5,6)=55; a=a+a' M=max(max(a)*n2; %M为充分大的正实数 a=a+(a=0)-eye(n)*M; path=zeros(n); for k=1:n for i=1:n for j=1:n if a(i,j)>a(i,k)+a(k,j) a(i,j)=a(i,k)+a(k,j); path(i,j)=k; end end end end a, path 我们使用LINGO9.0编写的FLOYD算法如下： model: sets: nodes/c1.c6/; link(nodes,nodes):w,path; !path标志最短路径上走过的顶点; endsets data: path=0; w=0; text(mydata1.txt)=writefor(nodes(i):writefor(nodes(j): format(w(i,j),' 10.0f'),newline(1); text(mydata1.txt)=write(newline(1); text(mydata1.txt)=writefor(nodes(i):writefor(nodes(j): format(path(i,j),' 10.0f'),newline(1); enddata calc: w(1,2)=50;w(1,4)=40;w(1,5)=25;w(1,6)=10; w(2,3)=15;w(2,4)=20;w(2,6)=25; w(3,4)=10;w(3,5)=20; w(4,5)=10;w(4,6)=25;w(5,6)=55; for(link(i,j):w(i,j)=w(i,j)+w(j,i); for(link(i,j) |i#ne#j:w(i,j)=if(w(i,j)#eq#0,10000,w(i,j); for(nodes(k):for(nodes(i):for(nodes(j): tm=smin(w(i,j),w(i,k)+w(k,j); path(i,j)=if(w(i,j)#gt# tm,k,path(i,j);w(i,j)=tm); endcalc end
