求大神解答，关于floyd算法

Araneider

这是2000年b题的一个floyd算法matlab程序。。。。。但是有些看不懂啊~~~那个大神指教一下~~~~

Floyd算法函数在matlab下的M函数文件如下：
function [D,path]=floyd(a)
, }: j: f- g# N9 k- }+ @) a3 j% x. hn=size(a,1);
D=a;path=zeros(n,n);
for i=1:n
( i& q9 }  `, Z    for j=1:n
        if D(i,j)~=inf
            path(i,j)=j;
        end
    end
end
for k=1:n
. Q5 F4 m0 ~4 u" j) h, _    for i=1:n
  a0 {1 V. S8 V/ p  l4 Z        for j=1:n
3 H, C7 R$ M: U1 _0 B            if D(i,k)+D(k,j)<D(i,j)
1 o# x4 S7 }$ f+ e4 g) Q0 b: v                D(i,j)=D(i,k)+D(k,j);
/ }8 c% n- S& ^4 f2 v" l: l% T5 c6 C                path(i,j)=path(i,k);
            end
        end
    end
end
2 h' ~/ o3 V# M( a- ]8 v上面是一个函数，这一部分可以看懂，但是下面这个求最小费的问题就看不懂了。。。。
ab=[1 1 2 3 4 5 6 7 8 9 10 11 12 13 15 16 17 18 19 20  20 22 23];
9 ~9 Y. P( v2 l/ M( i0 Y" I& N' p6 cbb=[ 14 15 15 16 19 18 23 24 10 10 11 15 13 14 16 17 19 19 20 21 22 23 24];
* y" W3 S: B* ]0 m- K  |w=[20 202 1200 690  690 462 70 30 450 80 1150 1100 306 195 720 520 170 88 160 70 320 160 290];
* |, L& @' \. f6 j. u% x" o; eab1=[1 2 4 5 6 7 8 9 10 11 14 15 16 17 18 33 34 35];
; v' J& M; w& G" g' Nbb1=[19 20 21 22 23 24 25 26 27 28 29 30 31 31 19 24 31 32];
. D! q1 a' E8 A' |9 b* H5 Fw1=[3 2 600 10 5 10 12 42 70 10 10 62 30 20  104 31 110 20];
a=sparse(ab,bb,w);
3 ]2 S# f& l: K1 R3 t$ q! la(24,24)=0;
' _) w  E3 d+ {4 P9 E- va=a+a’;
a=full(a);
' z0 ?. E) c7 S" R' ^for i=1:24
7 T$ {+ M! }: G& a1 e3 S    for j=1:24
        if(a(i,j)==0&i~=j)
            a(i,j)=inf;
& A" t. U" o  l9 h        end
    end
3 P6 f9 f# H" h7 O: a9 k* fend
[D,path]=floyd(a);
a1=sparse(ab1,bb1,w1);
: _# z2 }# }3 j8 z6 Q/ xa1(35,35)=0;
a1=a1+(a1)';
a1=full(a1);
# k4 r$ w  R4 B3 m/ g% Y8 xfor i=1:35
2 P$ S7 k! m( q# v0 Y" d" e" s& O/ N    for j=1:35
% ?: R; W1 v4 o- x        if(a1(i,j)==0&i~=j)
; O3 A& T1 K0 i6 R& ?) V4 a  v# P# w            a1(i,j)=inf;
# `) a* g3 v4 s        end
* z! i7 `7 q! ~; c1 [& H7 A1 Z    end
2 b# }% k# c" _' ?4 F8 aend
% @$ b. S: T: ~& g5 N  y9 Q% D[D1,path1]=floyd(a1);
$ Q: B' x/ r+ I& k2 A上面这一段应该是赋值求最短路了吧，，，但是这赋值是赋得什么值额？？？？有大神的话可以在后面注释一下。。。万分感谢。。。

467857726de

不错哦  谢谢楼主

Araneider

快来大神啊，快来大神啊

Araneider

上面那就是题目，，下面是给出的图
: `& d+ J- J) J& r0 I  `. V8 j

Araneider

　　钢管订购和运输（2000年网易杯全国大学生数学建模竞赛B题）
' p4 s7 L& [: d- S2 Z/ r　　   要铺设一条的输送天然气的主管道，如图所示。经筛选后可以生产这种主管道钢管的钢厂有。图中粗线表示铁路，单细线表示公路，双线表示要铺设的管道（假设沿管道或者原有公路，或者建有施工公路），圆圈（点） 表示火车站，
　　每段铁路、公路和管道旁的阿拉伯数字表示里程（单位km）。
　　     为方便计，1km主管道钢管称为1单位钢管。
" k' |: e: d/ D6 Y0 t# p　　  一个钢厂如果承担制造这种钢管，至少需要生产500个单位。钢厂在指定期限内能生产该钢管的最大数量为个单位，钢管出厂销价1单位钢管为万元，如下表：
I           1           2           3          4          5          6           7
) \0 w1 A3 U* v/ YSi        800        800        1000        2000        2000        2000        3000
Pi        160        155        155        160        155        150        160
+ x: I# v6 {( Z, d: ~　　一单位钢管的铁路运价如下表：
4 P* Q/ {3 h$ Y  O0 B9 K: U里程（km）        ≤300        301～350        351～400        401～450        451～500
运价（万元）        20        23        26        29        32
9 p! p( A0 [: k, Y' W  @里程（km）        501～600        601～700        701～800        801～900        901～1000
6 K4 @0 y; J1 T/ _5 a4 z8 ]; C运价（万元）        37        44        50        55        60
  W3 H2 l* g* W% \　　1000km以上每增加1至100km运价增加5万元。
　　   公路运输费用为1单位钢管每公里0·1万元（不足整公里部分按整公里计算）。
　　钢管可由铁路、公路运往铺设地点（不只是运到点，而是管道全线）。
1.请制定一个主管道钢管的订购和运输计划，使总费用最小（给出总费用）。
2.请就（1）的模型分析：哪个钢厂钢管的销价的变化对购运计划和总费用影响最大，哪个钢厂钢管的产量的上限的变化对购运计划和总费用的影响最大，并给出相应的数字结果。
3.如果要铺设的管道不是一条线，而是一个树形图，铁路、公路和管道构成网络，请就这种更一般的情况给出一种解决办法，并对图二按（1）的要求给出模型和结果.

Araneider

C:\Documents and Settings\Administrator\桌面

Araneider

　　管订购和运输（2000年网易杯全国大学生数学建模竞赛B题）
　　   要铺设一条的输送天然气的主管道，如图所示。经筛选后可以生产这种主管道钢管的钢厂有。图中粗线表示铁路，单细线表示公路，双线表示要铺设的管道（假设沿管道或者原有公路，或者建有施工公路），圆圈（点） 表示火车站，
　　每段铁路、公路和管道旁的阿拉伯数字表示里程（单位km）。
1 f+ {2 D0 `, F( {, Z4 X. y　　     为方便计，1km主管道钢管称为1单位钢管。
2 ^* w4 S: n2 ^+ [$ {% z( W; l　　  一个钢厂如果承担制造这种钢管，至少需要生产500个单位。钢厂在指定期限内能生产该钢管的最大数量为个单位，钢管出厂销价1单位钢管为万元，如下表：
% h4 z: e' a' o+ z/ N% mI           1           2           3          4          5          6           7
        800        800        1000        2000        2000        2000        3000
7 u( O6 _, d' ~2 L) G# K; x        160        155        155        160        155        150        160
　　一单位钢管的铁路运价如下表：
里程（km）        ≤300        301～350        351～400        401～450        451～500
运价（万元）        20        23        26        29        32
里程（km）        501～600        601～700        701～800        801～900        901～1000
" P$ B) s$ ^4 _3 ^运价（万元）        37        44        50        55        60
　　1000km以上每增加1至100km运价增加5万元。
　　   公路运输费用为1单位钢管每公里0·1万元（不足整公里部分按整公里计算）。
! {% e# w" Q% O. K7 M( g: Z9 }" `　　钢管可由铁路、公路运往铺设地点（不只是运到点，而是管道全线）。
请制定一个主管道钢管的订购和运输计划，使总费用最小（给出总费用）。
  ^% |! y9 W+ Q9 A请就（1）的模型分析：哪个钢厂钢管的销价的变化对购运计划和总费用影响最大，哪个钢厂钢管的产量的上限的变化对购运计划和总费用的影响最大，并给出相应的数字结果。
如果要铺设的管道不是一条线，而是一个树形图，铁路、公路和管道构成网络，请就这种更一般的情况给出一种解决办法，并对图二按（1）的要求给出模型和结果.

. P; K* z- Q- B. B' RC:\Documents and Settings\Administrator\桌面