Dijkstra、Floyd算法Matlab,Lingo实现

Dijkstra算法Matlab实现。%求一个点到其他各点的最短路径functionmin,path=dijkstra(w,start,terminal)%W是邻接矩阵应用举例:9,9,10;.,8,10,9;.,9,2,2;weight=inf*ones(n,n);fori=1:nweight(i,i)=0;endfori=1:size(edge,2)weight(edge(1,i),edge(2,i)=edge(3,i);enddis,path=dijkstra(weight,1,11)%start是起始点%terminal是终止点%min是最短路径长度%path是最短路径n=size(w,1);label(start)=0;f(start)=start;fori=1:nifi=startlabel(i)=inf;endends(1)=start;u=start;whilelength(s)nfori=1:nins=0;forj=1:length(s)ifi=s(j)ins=1;endendifins=0v=i;iflabel(v)(label(u)+w(u,v)label(v)=(label(u)+w(u,v);f(v)=u;endendendv1=0;k=inf;fori=1:nins=0;forj=1:length(s)ifi=s(j)ins=1;endendifins=Ov=i;ifklabel(v)k=label(v);v1=v;endendends(length(s)+1)=v1;u=v1;endmin=label(terminal);path(1)=terminal;i=1；whilepath(i)=startpath(i+1)=f(path(i);i=i+1;endpath(i)=start;L=length(path);path=path(L:-1:1);Floyd算法：matlab程序：%floyd算法，functionD,path,min1,path1=floyd(a,start,terminal)%a是邻接矩阵%start是起始点%terminal是终止点%D是最小权值表应用举例：a=0,50,inf,40,25,1050,0,15,20,inf,25inf,15,0,10,20,inf40,20,10,0,10,2525,inf,20,10,0,5510,25,inf,25,55,0;D,path=floyd(a)%path是最短路线表。D=a;n=size(D,1);path=zeros(n,n);fori=1:nforj=1:nifD(i,j)=infpath(i,j)=j;endendendfork=1:nfori=1:nforj=1:nifD(i,k)+D(k,j)D(i,j)D(i,j)=D(i,k)+D(k,j);path(i,j)=path(i,k);endendendendifnargin=3min1=D(start,terminal);m(1)=start;i=1；path1=;whilepath(m(i),terminal)=terminalk=i+1;m(k)=path(m(i),terminal);i=i+1;endm(i+1)=terminal;path1=m;endFloyd算法：Lingo程序：!用LINGO11.0编写的FLOYD算法如下；model:sets:nodes/c1.c6/;link(nodes,nodes):w,path;!path标志最短路径上走过的顶点；endsetsdata: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);enddatacalc: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):smin(w(i,j),w(i,k)+w(k,j);path(i,jif(w(i,j)#gt#tm,k,path(i,j);w(i,j)=tm);endcalcend无向图的最短路问题Lingomodel:sets:cities/1.11/;roads(cities,cities):w,x;endsetsdata:w=0;enddatacalc: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);endcalcn=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