floyd 的应用

附录

用matlab建立Floyd函数的M文件，编程如下： function [D,path]=floyd(a) n=size(a,1);

D=a;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)

问题一：

1)

用Floyd算法求铁路最短距离， 以7个钢管厂和17个中转点建立初始距离矩阵

?D?ij24*24，对于任意两点之

间的距离，如果两点之间有铁路直接连接， 其值为两点间铁路的距离；如果两点之间没有铁路直接连接，则其值为inf。 2)

用Floyd算法求公路最短距离，以15个铺设节点、17个中转点和S1、S6、S7三个钢管厂建立初始距离矩阵

?D1?3)

ij35*35，对于任意两点之间的距离，如果两点之间有公路直接连接，

其值为两点间公路的距离；如果两

点之间没有公路直接连接，则其值为inf。 用Floyd算法求铁路和公路最少费用，编程如下：

D(i,j)=20; case m2

D(i,j)=23; case m3

D(i,j)=26; case m4

D(i,j)=29; case m5

D(i,j)=32; case m6

D(i,j)=37; case m7

D(i,j)=44; case m8

D(i,j)=50; case m9

D(i,j)=55; case m0

D(i,j)=60; otherwise

D(i,j)=ceil((D(i,j)-1000)/100)*5+60; end end end

%距离转换为费用的程序

D1=D1*0.1; %把公路最短距离换算成公路最少费用

for k=1:300 m1(k)={k}; end

for k=1:50

m2(k)={300+k}; m3(k)={350+k}; m4(k)={400+k}; m5(k)={450+k}; end

for k=1:100

m6(k)={500+k}; m7(k)={600+k}; m8(k)={700+k}; m9(k)={800+k}; m0(k)={900+k}; end

for i=1:24

for j=1:24 %把铁路最短距离换算成铁路最少费用

switch D(i,j) case 0

D(i,j)=0; case m1

1

%c矩阵表示七个钢管生产厂到十五个铺设节点之间的距离，先把它们都设成20000（任意一个钢管厂到任意一个铺设节点之间的距离不会超过20000），然后用 for 循环求出最小值

c=[20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000; 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000; 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000; 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000; 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000; 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000; 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000];

for i=1:7 %7个钢管生产厂 for k=1:15 个铺设节点 for j=8:24 %7个钢管生产厂和17个中转点，i=1，表示第一个钢管生产厂，j=8，表示第一个中转点

if c(i,k)>D(i,j)+D1(k,j+8) c(i,k)=D(i,j)+D1(k,j+8);

%对于所有中转点，在铁路网和公路网上的下标相差8

c(i,k)=D(i,1)+D1(k,33);

3代表第一个钢管生产厂S1点

end

if c(i,k)>D(i,6)+D1(k,34) c(i,k)=D(i,6)+D1(k,34);

4代表第六个钢管生产厂S6点

end

if c(i,k)>D(i,7)+D1(k,35) c(i,k)=D(i,7)+D1(k,35);

5代表第七个钢管生产厂S7点

end

end

%因为S1,S6,S7这三个钢管厂有公路直接连接到铺设节点，所以把这三个点单独处理 end

end end end end for i=1:7

for k=1:15

if c(i,k)>D(i,1)+D1(k,33) 运行结果如下：

问题一用Lingo软件求解的编程：

model: sets:

supply/S1..S7/:p,s,t; need/A1..A15/:L,R,b; links(supply,need):c,x; endsets data:

s=800 800 1000 2000 2000 2000 3000;

b=104,301,750,606,194,205,201,680,480,300,220,210,420,500,;

c=170.7 160.3 140.2 98.6 38.0 20.5 3.1 21.2 64.2 92.0 96.0 106.0 121.2 128.0 142.0 215.7 205.3 190.2 171.6 111.0 95.5 86.0 71.2 114.2 142.0 146.0 156.0 171.2 178.0 192.0

2

230.7 220.3 200.2 181.6 121.0 105.5 96.0 86.2 48.2 82.0 86.0 96.0 111.2 118.0 132.0 260.7 250.3 235.2 216.6 156.0 140.5 131.0 116.2 84.2 62.0 51.0 61.0 76.2 83.0 97.0 255.7 245.3 225.2 206.6 146.0 130.5 121.0 111.2 79.2 57.0 33.0 51.0 71.2 73.0 87.0 265.7 255.3 235.2 216.6 156.0 140.5 131.0 121.2 84.2 62.0 51.0 45.0 26.2 11.0 28.0 275.7 265.3 245.2 226.6 166.0 150.5 141.0 131.2 99.2 77.0 66.0 56.0 38.2 26.0 2.0;

enddata

min=@sum(links(i,j):(p(i)+c(i,j))*x(i,j))+0.05*@sum(need(j):L(j)^2+L(j)+R(j)^2+R(j)); @for(supply(i):@sum(need(j):x(i,j))>=500*t(i)); @for(supply(i):@sum(need(j):x(i,j))<=s(i)*t(i)); @for(supply(i):@bin(t(i)));

@for(need(j):@sum(supply(i):x(i,j))=L(j)+R(j)); @for(need(j)|j#NE#15:b(j)=R(j)+L(j+1)); R(15)=0;L(1)=0;

@gin(@sum(links(i,j):x(i,j)));

p(1)=160;p(2)=155;p(3)=155;p(4)=160;p(5)=155;p(6)=150;p(7)=160; end

问题三

（1） 用Floyd算法求铁路最短距离，matlab编程与问题一相同

（2） 用Floyd算法求公路最短距离，以21个铺设节点和14个中转点建立初始距离矩阵

义与前面D矩阵相似

（3） 再次调用距离转费用程序，求出铁路和公路最少费用

?D2?ij35*35，D2矩阵的意

%h矩阵表示七个钢管生产厂到21个铺设节点之间的距离，先把它们都设成20000（任意一个钢管厂到任意一个铺设节点之间的距离不会超过20000），然后用 for 循环求出最小值

h=[20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000;

20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000;

20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000;

20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000;

20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000;

20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000;

20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000];

3

for i=1:7

m=1; for

k=[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,24,27,28,29,30,34] for j=8:24

if h(i,m)>D(i,j)+D2(k,j+8) h(i,m)=D(i,j)+D2(k,j+8); end end m=m+1; end end

for i=1:7 m=1; for

k=[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,24,27,28,29,30,34]

if h(i,m)>D(i,1)+D2(k,33) h(i,m)=D(i,1)+D2(k,33); end

if h(i,m)>D(i,6)+D2(k,34) h(i,m)=D(i,6)+D2(k,34); end

if h(i,m)>D(i,7)+D2(k,35) h(i,m)=D(i,7)+D2(k,35); end m=m+1; end end

4

运行结果如下：

问题三用软件Lingo编程：

model: sets:

supply/S1..S7/:p,s,t; need/A1..A21/:L,R,Z,b; links(supply,need):c,x; endsets data:

p=160 155 155

160 155 150 160;

s=800 800 1000 2000 2000 2000 3000;

b=104,301,750,606,194,205,201,680,480,300,220,210,420,500,,42,10,130,190,260,100;

c=170.7, 160.3, 140.2, 98.6, 38, 20.5, 3.1, 21.2, 64.2, 92, 96, 106, 121.2, 128, 142, 60, 95, 100, 105, 115, 125 215.7, 205.3, 190.2, 171.6, 111, 95.5, 86, 71.2, 114.2, 142, 146, 156, 171.2, 178, 192, 110, 145, 150, 155, 165, 175 230.7, 220.3, 200.2, 181.6, 121, 105.5, 96, 86.2, 48.2, 82, 86, 96, 111.2, 118, 132, 44, 85, 90, 95, 105, 115 260.7, 250.3, 235.2, 216.6, 156, 140.5, 131, 116.2, 84.2, 62, 51, 61, 76.2, 83, 97, 80, 50, 55, 60, 70, 80 255.7, 245.3, 225.2, 206.6, 146, 130.5, 121, 111.2, 79.2, 57, 33, 51, 71.2, 73, 87, 75, 32, 45, 50, 65, 75 265.7, 255.3, 235.2, 216.6, 156, 140.5, 131, 121.2, 84.2, 62, 51, 37, 16.2, 11, 28, 80, 50, 37, 36, 10, 0 275.7, 265.3, 245.2, 226.6, 166, 150.5, 141, 131.2, 99.2, 77, 64, 56, 38.2, 26, 2, 95, 63, 50, 55, 32, 26; enddata

min=@sum(links(i,j):(p(i)+c(i,j))*x(i,j))+0.05*(@sum(need(j)|j#GE#2 #AND#

j#LE#21 :L(j)^2+L(j))+@sum(need(j)|j#LE#14 :R(j)^2+R(j))+@sum(need(j)|j#EQ#9 #OR# j#EQ#11 #OR# j#EQ#17 :Z(j)^2+Z(j))+@sum(need(j)|j#EQ#17 #OR# j#EQ#19 #OR# j#EQ#20 :R(j)^2+R(j)));

@for(supply(i):@sum(need(j):x(i,j))>=500*t(i)); @for(supply(i):@sum(need(j):x(i,j))<=s(i)*t(i)); @for(supply(i):@bin(t(i)));

@for(need(j)|j#NE#9 #AND# j#NE#11 #AND# j#NE#17:Z(j)=0); @for(need(j):@sum(supply(i):x(i,j))=L(j)+R(j)+Z(j)); @for(need(j)|j#LT#15:b(j)=R(j)+L(j+1));

b(16)=Z(9)+L(16);b(17)=Z(11)+Z(17); b(18)=L(17)+L(18);b(19)=R(17)+L(19); b(20)=R(19)+L(20);b(21)=R(20)+L(21); @gin(@sum(links(i,j):x(i,j))); end

1

附录

用matlab建立Floyd函数的M文件，编程如下： function [D,path]=floyd(a) n=size(a,1);

D=a;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)

问题一：

4)

用Floyd算法求铁路最短距离， 以7个钢管厂和17个中转点建立初始距离矩阵

?D?ij24*24，对于任意两点之

间的距离，如果两点之间有铁路直接连接， 其值为两点间铁路的距离；如果两点之间没有铁路直接连接，则其值为inf。 5)

用Floyd算法求公路最短距离，以15个铺设节点、17个中转点和S1、S6、S7三个钢管厂建立初始距离矩阵

?D1?6)

ij35*35，对于任意两点之间的距离，如果两点之间有公路直接连接，

其值为两点间公路的距离；如果两

点之间没有公路直接连接，则其值为inf。 用Floyd算法求铁路和公路最少费用，编程如下：

D(i,j)=20; case m2

D(i,j)=23; case m3

D(i,j)=26; case m4

D(i,j)=29; case m5

D(i,j)=32; case m6

D(i,j)=37; case m7

D(i,j)=44; case m8

D(i,j)=50; case m9

D(i,j)=55; case m0

D(i,j)=60; otherwise

D(i,j)=ceil((D(i,j)-1000)/100)*5+60; end end end

%距离转换为费用的程序

D1=D1*0.1; %把公路最短距离换算成公路最少费用

for k=1:300 m1(k)={k}; end

for k=1:50

m2(k)={300+k}; m3(k)={350+k}; m4(k)={400+k}; m5(k)={450+k}; end

for k=1:100

m6(k)={500+k}; m7(k)={600+k}; m8(k)={700+k}; m9(k)={800+k}; m0(k)={900+k}; end

for i=1:24

for j=1:24 %把铁路最短距离换算成铁路最少费用

switch D(i,j) case 0

D(i,j)=0; case m1

2

%c矩阵表示七个钢管生产厂到十五个铺设节点之间的距离，先把它们都设成20000（任意一个钢管厂到任意一个铺设节点之间的距离不会超过20000），然后用 for 循环求出最小值

c=[20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000; 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000; 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000; 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000; 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000; 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000; 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000];

for i=1:7 %7个钢管生产厂 for k=1:15 个铺设节点 for j=8:24 %7个钢管生产厂和17个中转点，i=1，表示第一个钢管生产厂，j=8，表示第一个中转点

if c(i,k)>D(i,j)+D1(k,j+8) c(i,k)=D(i,j)+D1(k,j+8);

%对于所有中转点，在铁路网和公路网上的下标相差8

c(i,k)=D(i,1)+D1(k,33);

3代表第一个钢管生产厂S1点

end

if c(i,k)>D(i,6)+D1(k,34) c(i,k)=D(i,6)+D1(k,34);

4代表第六个钢管生产厂S6点

end

if c(i,k)>D(i,7)+D1(k,35) c(i,k)=D(i,7)+D1(k,35);

5代表第七个钢管生产厂S7点

end

end

%因为S1,S6,S7这三个钢管厂有公路直接连接到铺设节点，所以把这三个点单独处理 end

end end end end for i=1:7

for k=1:15

if c(i,k)>D(i,1)+D1(k,33) 运行结果如下：

问题一用Lingo软件求解的编程：

model: sets:

supply/S1..S7/:p,s,t; need/A1..A15/:L,R,b; links(supply,need):c,x; endsets data:

s=800 800 1000 2000 2000 2000 3000;

b=104,301,750,606,194,205,201,680,480,300,220,210,420,500,;

c=170.7 160.3 140.2 98.6 38.0 20.5 3.1 21.2 64.2 92.0 96.0 106.0 121.2 128.0 142.0 215.7 205.3 190.2 171.6 111.0 95.5 86.0 71.2 114.2 142.0 146.0 156.0 171.2 178.0 192.0

3

230.7 220.3 200.2 181.6 121.0 105.5 96.0 86.2 48.2 82.0 86.0 96.0 111.2 118.0 132.0 260.7 250.3 235.2 216.6 156.0 140.5 131.0 116.2 84.2 62.0 51.0 61.0 76.2 83.0 97.0 255.7 245.3 225.2 206.6 146.0 130.5 121.0 111.2 79.2 57.0 33.0 51.0 71.2 73.0 87.0 265.7 255.3 235.2 216.6 156.0 140.5 131.0 121.2 84.2 62.0 51.0 45.0 26.2 11.0 28.0 275.7 265.3 245.2 226.6 166.0 150.5 141.0 131.2 99.2 77.0 66.0 56.0 38.2 26.0 2.0;

enddata

min=@sum(links(i,j):(p(i)+c(i,j))*x(i,j))+0.05*@sum(need(j):L(j)^2+L(j)+R(j)^2+R(j)); @for(supply(i):@sum(need(j):x(i,j))>=500*t(i)); @for(supply(i):@sum(need(j):x(i,j))<=s(i)*t(i)); @for(supply(i):@bin(t(i)));

@for(need(j):@sum(supply(i):x(i,j))=L(j)+R(j)); @for(need(j)|j#NE#15:b(j)=R(j)+L(j+1)); R(15)=0;L(1)=0;

@gin(@sum(links(i,j):x(i,j)));

p(1)=160;p(2)=155;p(3)=155;p(4)=160;p(5)=155;p(6)=150;p(7)=160; end

问题三

（4） 用Floyd算法求铁路最短距离，matlab编程与问题一相同

（5） 用Floyd算法求公路最短距离，以21个铺设节点和14个中转点建立初始距离矩阵

义与前面D矩阵相似

（6） 再次调用距离转费用程序，求出铁路和公路最少费用

?D2?ij35*35，D2矩阵的意

%h矩阵表示七个钢管生产厂到21个铺设节点之间的距离，先把它们都设成20000（任意一个钢管厂到任意一个铺设节点之间的距离不会超过20000），然后用 for 循环求出最小值

h=[20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000;

20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000;

20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000;

20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000;

20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000;

20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000;

20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000 20000];

4

for i=1:7

m=1; for

k=[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,24,27,28,29,30,34] for j=8:24

if h(i,m)>D(i,j)+D2(k,j+8) h(i,m)=D(i,j)+D2(k,j+8); end end m=m+1; end end

for i=1:7 m=1;

运行结果如下：

for

k=[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,24,27,28,29,30,34]

if h(i,m)>D(i,1)+D2(k,33) h(i,m)=D(i,1)+D2(k,33); end

if h(i,m)>D(i,6)+D2(k,34) h(i,m)=D(i,6)+D2(k,34); end

if h(i,m)>D(i,7)+D2(k,35) h(i,m)=D(i,7)+D2(k,35); end m=m+1; end end

问题三用软件Lingo编程：

model: sets:

supply/S1..S7/:p,s,t; need/A1..A21/:L,R,Z,b; links(supply,need):c,x; endsets data:

p=160 155 155

160 155 150 160;

s=800 800 1000 2000 2000 2000 3000;

b=104,301,750,606,194,205,201,680,480,300,220,210,420,500,,42,10,130,190,260,100;

c=170.7, 160.3, 140.2, 98.6, 38, 20.5, 3.1, 21.2, 64.2, 92, 96, 106, 121.2, 128, 142, 60, 95, 100, 105, 115, 125 215.7, 205.3, 190.2, 171.6, 111, 95.5, 86, 71.2, 114.2, 142, 146, 156, 171.2, 178, 192, 110, 145, 150, 155, 165, 175 230.7, 220.3, 200.2, 181.6, 121, 105.5, 96, 86.2, 48.2, 82, 86, 96, 111.2, 118, 132, 44, 85, 90, 95, 105, 115 260.7, 250.3, 235.2, 216.6, 156, 140.5, 131, 116.2, 84.2, 62, 51, 61, 76.2, 83, 97, 80, 50, 55, 60, 70, 80 255.7, 245.3, 225.2, 206.6, 146, 130.5, 121, 111.2, 79.2, 57, 33, 51, 71.2, 73, 87, 75, 32, 45, 50, 65, 75 265.7, 255.3, 235.2, 216.6, 156, 140.5, 131, 121.2, 84.2, 62, 51, 37, 16.2, 11, 28, 80, 50, 37, 36, 10, 0 275.7, 265.3, 245.2, 226.6, 166, 150.5, 141, 131.2, 99.2, 77, 64, 56, 38.2, 26, 2, 95, 63, 50, 55, 32, 26; enddata

min=@sum(links(i,j):(p(i)+c(i,j))*x(i,j))+0.05*(@sum(need(j)|j#GE#2 #AND#

j#LE#21 :L(j)^2+L(j))+@sum(need(j)|j#LE#14 :R(j)^2+R(j))+@sum(need(j)|j#EQ#9 #OR# j#EQ#11 #OR# j#EQ#17 :Z(j)^2+Z(j))+@sum(need(j)|j#EQ#17 #OR# j#EQ#19 #OR# j#EQ#20 :R(j)^2+R(j)));

@for(supply(i):@sum(need(j):x(i,j))>=500*t(i));

5

@for(supply(i):@sum(need(j):x(i,j))<=s(i)*t(i)); @for(supply(i):@bin(t(i)));

@for(need(j)|j#NE#9 #AND# j#NE#11 #AND# j#NE#17:Z(j)=0); @for(need(j):@sum(supply(i):x(i,j))=L(j)+R(j)+Z(j)); @for(need(j)|j#LT#15:b(j)=R(j)+L(j+1));

b(16)=Z(9)+L(16);b(17)=Z(11)+Z(17); b(18)=L(17)+L(18);b(19)=R(17)+L(19); b(20)=R(19)+L(20);b(21)=R(20)+L(21); @gin(@sum(links(i,j):x(i,j))); end

6

本文来源：https://www.bwwdw.com/article/xeqd.html