Dijkstra、Floyd算法Matlab-Lingo实现

Dijkstra、Floyd算法Matlab-Lingo实现

Dijkstra算法Matlab实现。

%求一个点到其他各点的最短路径

function [min,path]=dijkstra(w,start,terminal)

%W是邻接矩阵

%start是起始点Array %terminal是终止点

%min是最短路径长度

%path是最短路径

n=size(w,1);

label(start)=0;

f(start)=start;

for i=1:n

if i~=start

label(i)=inf;

end

end

s(1)=start;

u=start;

while length(s)

for i=1:n

ins=0;

for j=1:length(s)

if i==s(j)

ins=1;

end

end

if ins==0

v=i;

if label(v)>(label(u)+w(u,v))

label(v)=(label(u)+w(u,v));

f(v)=u;

end

end

end

v1=0;

k=inf;

for i=1:n

ins=0;

for j=1:length(s)

if i==s(j)

ins=1;

end

end

if ins==0

v=i;

if k>label(v)

k=label(v);

v1=v;

end

end

end

s(length(s)+1)=v1;

u=v1;

end

min=label(terminal);

path(1)=terminal;

i=1;

while path(i)~=start

path(i+1)=f(path(i));

i=i+1 ;

end

path(i)=start;

L=length(path);

path=path(L:-1:1);

Floyd算法：matlab程序：

%floyd算法，

function [D,path,min1,path1]=floyd(a,start,terminal)

%a是邻接矩阵

%start是起始点

%terminal是终止点

%D是最小权值表

D=a;n=size(D,1);

path=zeros(n,n);

for i=1:n

for j=1:n

if D(i,j)~=inf

path(i,j)=j;

end

end

end

for k=1:n

for i=1:n

for j=1:n

if D(i,k)+D(k,j)

D(i,j)=D(i,k)+D(k,j);

path(i,j)=path(i,k);

end

end

end

end

if nargin==3

min1=D(start,terminal);

m(1)=start;

i=1;

path1=[ ];

while path(m(i),terminal)~=terminal

k=i+1;

m(k)=path(m(i),terminal);

i=i+1;

end

m(i+1)=terminal;

path1=m;

end

1 6 5 5 5 6

6 2 3 4 4 6

5 2 3 4 5 4

5 2 3 4 5 6

1 4 3 4 5 1

1 2 4 4 1 6

Floyd算法：Lingo程序：

!用LINGO11.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

无向图的最短路问题 Lingo

model:

sets:

cities/1..5/;

roads(cities,cities):w,x;

endsets

data:

w=0;

enddata

calc:

w(1,2)=41;w(1,3)=59;w(1,4)=189;w(1,5)=81;

w(2,3)=27;w(2,4)=238;w(2,5)=94;

w(3,4)=212;w(3,5)=89;w(4,5)=171;

@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

Lingo编的

sets:

dian/a b1 b2 c1 c2 c3 d/:;

link(dian,dian)/a,b1 a,b2 b1,c1 b1,c2 b1,c3 b2,c1 b2,c2 b2,c3 c1,d c2,d c3,d/:x,w; endsets

data:

w=2 4 3 3 1 2 3 1 1 3 4;

enddata

min=@sum(link:w*x);

@for(link:@bin(x));

n=@size(dian);

@sum(link(i,j)|i#eq#1:x(i,j))=1;

@sum(link(j,i)|i#eq#n:x(j,i))=1;

@for(dian(k)|k#ne#1#and#k#ne#n:

@sum(link(i,k):x(i,k))=@sum(link(k,i):x(k,i)));

sets:

dian/1..5/:level; !level(i)表示点i的水平，用来防止生产圈;

link(dian,dian):d,x;

endsets

data:

d=0 41 59 189 81

41 0 27 238 94

59 27 0 212 89

189 238 212 0 171

81 94 89 171 0;

enddata

n=@size(dian);

min=@sum(link(i,j)|i#ne#j:d(i,j)*x(i,j));

@sum(dian(j)|j#gt#1:x(1,j))>1;

@for(dian(i)|i#gt#1:@sum(dian(j)|j#ne#i:x(j,i))=1);

@for(dian(i)|i#gt#1:@for(dian(j)|j#ne#i#and#j#gt#1:level(j)>level(i)+x(i,j)-(n-2)* (1-x(i,j))+(n-3)*x(j,i)));

@for(dian(i)|i#gt#1:level(i)

@for(dian(i)|i#gt#1:@bnd(1,level(i),100000));

@for(link:@bin(x));

（注：可编辑下载，若有不当之处，请指正，谢谢!）