QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 4421|回复: 6
打印 上一主题 下一主题

[问题求助] 求大神解答,关于floyd算法

[复制链接]
字体大小: 正常 放大
Araneider        

8

主题

4

听众

114

积分

升级  7%

  • TA的每日心情
    难过
    2012-9-7 13:32
  • 签到天数: 21 天

    [LV.4]偶尔看看III

    自我介绍
    一名新人

    群组学术交流B

    群组学术交流A

    群组全国大学生数学建模竞

    群组建模讨论组

    群组竞赛备战群

    跳转到指定楼层
    1#
    发表于 2012-8-24 16:54 |只看该作者 |倒序浏览
    |招呼Ta 关注Ta
    这是2000年b题的一个floyd算法matlab程序。。。。。但是有些看不懂啊~~~那个大神指教一下~~~~
    . J) i" G0 W  t) I6 |# V  y
    ( c. u7 K$ G( U/ O. i6 oFloyd算法函数在matlab下的M函数文件如下:
    & u8 h9 r! T# T6 cfunction [D,path]=floyd(a)
    3 ?# \! z' t" l" P# r2 @$ cn=size(a,1);
    ' b1 Q1 h  }  P; X6 `) WD=a;path=zeros(n,n);7 E. d4 h4 {; W3 m& G% n; d, R+ R
    for i=1:n
    5 p+ z" `9 Z$ X5 v- m# g    for j=1:n
    ' t* {: ?: X1 H: a; |2 G- G        if D(i,j)~=inf
    + _5 J, K# B9 p, v; A, v# n0 A9 |9 d) c            path(i,j)=j;! W  o3 b# [7 ^7 }( H
            end
    , |- s7 x( w, P    end) R! h+ i, j+ I( a2 S( C2 c
    end
    " ?: B4 j& P1 J9 K. K: gfor k=1:n
    3 q2 m0 q, T. a4 D! z5 R: _    for i=1:n
    . }) V' Z& ]) }" ?9 k$ z5 @/ O1 e        for j=1:n4 \% b) ~% A' E- C9 {$ J
                if D(i,k)+D(k,j)<D(i,j)
      I; {- {+ N5 m& T  w1 c                D(i,j)=D(i,k)+D(k,j);
    7 V1 B& E4 H/ }. r3 D6 h4 P                path(i,j)=path(i,k);
    $ u3 p5 n( `' j+ Y" A2 _            end
    : y) Y! d0 m% H6 X( w) `( M        end
    & h# _9 {* a) Z' R3 g1 U6 S    end% L: A) y" X3 D  q
    end
    3 \2 ^& `, ~2 D0 }% D( Q3 t. l上面是一个函数,这一部分可以看懂,但是下面这个求最小费的问题就看不懂了。。。。5 T; ^+ s+ y2 j/ y3 u: y- h
    ab=[1 1 2 3 4 5 6 7 8 9 10 11 12 13 15 16 17 18 19 20  20 22 23];  u* S& {1 I) e8 h
    bb=[ 14 15 15 16 19 18 23 24 10 10 11 15 13 14 16 17 19 19 20 21 22 23 24];
    6 r1 @/ Q6 L$ _! `w=[20 202 1200 690  690 462 70 30 450 80 1150 1100 306 195 720 520 170 88 160 70 320 160 290];/ a- g( P2 G0 F- f! G' G/ r
    ab1=[1 2 4 5 6 7 8 9 10 11 14 15 16 17 18 33 34 35];& t& H2 V# \/ |! n  O8 c
    bb1=[19 20 21 22 23 24 25 26 27 28 29 30 31 31 19 24 31 32];
    . H' l5 j/ Z6 B% s  \: qw1=[3 2 600 10 5 10 12 42 70 10 10 62 30 20  104 31 110 20];
    8 C* [8 \* S" v! Y! P4 Ua=sparse(ab,bb,w);
    6 _( @+ R& F& u% sa(24,24)=0;# ]. {6 t, p' M
    a=a+a’;
    9 r+ G9 P. y5 k9 J7 ~a=full(a);
    ( v! u4 D& h! m. \/ w* n" r0 t5 L0 F  wfor i=1:24
    5 T8 {- n% }" T" ]" N: c) O    for j=1:24
    % i) ]/ F2 f% B( ?) D4 r        if(a(i,j)==0&i~=j), P/ j% M+ _0 W1 s$ Z% b2 B
                a(i,j)=inf;6 @& S) l" E: i* S4 h& `! K
            end$ C1 g4 B1 t; U  K
        end* k$ g3 R$ m9 n% x( e
    end
    7 f9 A; {# Q$ u( o- s5 e[D,path]=floyd(a);" \' H. v; `# n' O7 n5 U
    a1=sparse(ab1,bb1,w1);" D7 E* A6 q4 T6 M) l% |% ~# r" Q
    a1(35,35)=0;
    " I/ k* I2 ?: w8 ta1=a1+(a1)';' v2 e) G8 t* \2 H
    a1=full(a1);
    + M2 q1 \! f6 @$ Q% `for i=1:35
    0 y0 H5 S/ e) T8 I* n" _+ t; o    for j=1:35% p, c% I+ L4 f9 f
            if(a1(i,j)==0&i~=j)/ O8 e; b1 D7 W
                a1(i,j)=inf;0 [6 x1 E0 `( ]$ b& l0 w
            end
    ! x. ^2 F! S# J6 C9 O    end
    ! y' Q4 w! n' Q3 q: T* r# jend. ]" E& h0 t, N+ v6 m9 R" m- W$ h- [
    [D1,path1]=floyd(a1);
    ! I4 |8 t* p, Y( [: @上面这一段应该是赋值求最短路了吧,,,但是这赋值是赋得什么值额????有大神的话可以在后面注释一下。。。万分感谢。。。
    zan
    转播转播0 分享淘帖0 分享分享0 收藏收藏0 支持支持0 反对反对0 微信微信
    Araneider        

    8

    主题

    4

    听众

    114

    积分

    升级  7%

  • TA的每日心情
    难过
    2012-9-7 13:32
  • 签到天数: 21 天

    [LV.4]偶尔看看III

    自我介绍
    一名新人

    群组学术交流B

    群组学术交流A

    群组全国大学生数学建模竞

    群组建模讨论组

    群组竞赛备战群

      管订购和运输(2000年网易杯全国大学生数学建模竞赛B题). l! S4 m+ N! V& K
         要铺设一条的输送天然气的主管道,如图所示。经筛选后可以生产这种主管道钢管的钢厂有。图中粗线表示铁路,单细线表示公路,双线表示要铺设的管道(假设沿管道或者原有公路,或者建有施工公路),圆圈(点) 表示火车站,
    ( Y) C4 S3 [' Q0 Q; W  每段铁路、公路和管道旁的阿拉伯数字表示里程(单位km)。
    ' I) V  \, M2 o( L" o# \       为方便计,1km主管道钢管称为1单位钢管。
    . \, y( n% n/ r  R  D    一个钢厂如果承担制造这种钢管,至少需要生产500个单位。钢厂在指定期限内能生产该钢管的最大数量为个单位,钢管出厂销价1单位钢管为万元,如下表:2 V) K  J5 H+ g! l2 {
    I           1           2           3          4          5          6           7$ w+ E; y" t+ Q
            800        800        1000        2000        2000        2000        3000
    3 Y: w, s3 G/ d        160        155        155        160        155        150        160) p( n0 p$ p8 |+ O6 p7 e" p9 l8 s
      一单位钢管的铁路运价如下表:  @% f# r7 e' C: A8 r- h
    里程(km)        ≤300        301~350        351~400        401~450        451~500
    8 `8 }/ ?$ j6 l% b. {! S5 F运价(万元)        20        23        26        29        32+ w  `+ Y/ Z2 @, k- \5 e: i, Q
    里程(km)        501~600        601~700        701~800        801~900        901~1000/ x% J9 i1 m! v/ p* ^# B
    运价(万元)        37        44        50        55        60
    6 K* V: B% x/ n7 [4 ]  1000km以上每增加1至100km运价增加5万元。7 p3 j- D0 @- w, |1 D
         公路运输费用为1单位钢管每公里0·1万元(不足整公里部分按整公里计算)。3 u6 f8 J  N+ D1 L7 Z
      钢管可由铁路、公路运往铺设地点(不只是运到点,而是管道全线)。) k) [, V' o+ v) ?6 ]
    请制定一个主管道钢管的订购和运输计划,使总费用最小(给出总费用)。
    9 y/ ]( d* x! x4 Z请就(1)的模型分析:哪个钢厂钢管的销价的变化对购运计划和总费用影响最大,哪个钢厂钢管的产量的上限的变化对购运计划和总费用的影响最大,并给出相应的数字结果。
    & `* r9 O1 c$ z/ V8 R9 {如果要铺设的管道不是一条线,而是一个树形图,铁路、公路和管道构成网络,请就这种更一般的情况给出一种解决办法,并对图二按(1)的要求给出模型和结果.
    6 l5 O( k& S4 ~# \$ w  B: R9 n2 x) |# ]2 ]  }
    C:\Documents and Settings\Administrator\桌面
    回复

    使用道具 举报

    Araneider        

    8

    主题

    4

    听众

    114

    积分

    升级  7%

  • TA的每日心情
    难过
    2012-9-7 13:32
  • 签到天数: 21 天

    [LV.4]偶尔看看III

    自我介绍
    一名新人

    群组学术交流B

    群组学术交流A

    群组全国大学生数学建模竞

    群组建模讨论组

    群组竞赛备战群

    回复

    使用道具 举报

    Araneider        

    8

    主题

    4

    听众

    114

    积分

    升级  7%

  • TA的每日心情
    难过
    2012-9-7 13:32
  • 签到天数: 21 天

    [LV.4]偶尔看看III

    自我介绍
    一名新人

    群组学术交流B

    群组学术交流A

    群组全国大学生数学建模竞

    群组建模讨论组

    群组竞赛备战群

      钢管订购和运输(2000年网易杯全国大学生数学建模竞赛B题): y2 T0 e& r1 D% E5 ^$ W  W, H
         要铺设一条的输送天然气的主管道,如图所示。经筛选后可以生产这种主管道钢管的钢厂有。图中粗线表示铁路,单细线表示公路,双线表示要铺设的管道(假设沿管道或者原有公路,或者建有施工公路),圆圈(点) 表示火车站,
    / Y6 m! K* T3 P& n  每段铁路、公路和管道旁的阿拉伯数字表示里程(单位km)。: G5 Z  h) X- A; h: P5 r) ?
           为方便计,1km主管道钢管称为1单位钢管。$ n9 i( [! z: v4 y* R  o
        一个钢厂如果承担制造这种钢管,至少需要生产500个单位。钢厂在指定期限内能生产该钢管的最大数量为个单位,钢管出厂销价1单位钢管为万元,如下表:
    % [: n: R2 Y+ {% E3 QI           1           2           3          4          5          6           7
    & w9 {0 `- ~- p4 pSi        800        800        1000        2000        2000        2000        30000 V& G5 l/ m: z7 K* {( i
    Pi        160        155        155        160        155        150        160
    / ^2 U' f! F3 z  一单位钢管的铁路运价如下表:
      X' r5 ?! k2 e里程(km)        ≤300        301~350        351~400        401~450        451~500
    ( @( i8 p9 v% ~" b/ `3 l7 L运价(万元)        20        23        26        29        32$ r- s' ]5 M# |3 s: h; C% x
    里程(km)        501~600        601~700        701~800        801~900        901~1000
    ! _% {: C: i) y& ^运价(万元)        37        44        50        55        60
    - [0 P3 R2 O1 z. a" o  1000km以上每增加1至100km运价增加5万元。
      I/ m/ @' [* `4 O     公路运输费用为1单位钢管每公里0·1万元(不足整公里部分按整公里计算)。
    , i1 [; C. M  b% ^0 s  钢管可由铁路、公路运往铺设地点(不只是运到点,而是管道全线)。" r* _$ d, F' o  j7 i, B
    1.请制定一个主管道钢管的订购和运输计划,使总费用最小(给出总费用)。
    7 r. E, s; f+ b5 H6 w. i4 Q2.请就(1)的模型分析:哪个钢厂钢管的销价的变化对购运计划和总费用影响最大,哪个钢厂钢管的产量的上限的变化对购运计划和总费用的影响最大,并给出相应的数字结果。
    ( k' f4 {# m, d1 m( K* {3.如果要铺设的管道不是一条线,而是一个树形图,铁路、公路和管道构成网络,请就这种更一般的情况给出一种解决办法,并对图二按(1)的要求给出模型和结果.
    回复

    使用道具 举报

    Araneider        

    8

    主题

    4

    听众

    114

    积分

    升级  7%

  • TA的每日心情
    难过
    2012-9-7 13:32
  • 签到天数: 21 天

    [LV.4]偶尔看看III

    自我介绍
    一名新人

    群组学术交流B

    群组学术交流A

    群组全国大学生数学建模竞

    群组建模讨论组

    群组竞赛备战群

    回复

    使用道具 举报

    Araneider        

    8

    主题

    4

    听众

    114

    积分

    升级  7%

  • TA的每日心情
    难过
    2012-9-7 13:32
  • 签到天数: 21 天

    [LV.4]偶尔看看III

    自我介绍
    一名新人

    群组学术交流B

    群组学术交流A

    群组全国大学生数学建模竞

    群组建模讨论组

    群组竞赛备战群

    回复

    使用道具 举报

    3

    主题

    7

    听众

    179

    积分

    升级  39.5%

  • TA的每日心情
    擦汗
    2015-1-22 15:49
  • 签到天数: 21 天

    [LV.4]偶尔看看III

    国际赛参赛者

    自我介绍
    我是本科在校学生,从小就喜欢数学,希望可以在这里学到想要的东西。。。

    群组学术交流B

    回复

    使用道具 举报

    您需要登录后才可以回帖 登录 | 注册地址

    qq
    收缩
    • 电话咨询

    • 04714969085
    fastpost

    关于我们| 联系我们| 诚征英才| 对外合作| 产品服务| QQ

    手机版|Archiver| |繁體中文 手机客户端  

    蒙公网安备 15010502000194号

    Powered by Discuz! X2.5   © 2001-2013 数学建模网-数学中国 ( 蒙ICP备14002410号-3 蒙BBS备-0002号 )     论坛法律顾问:王兆丰

    GMT+8, 2026-9-9 17:32 , Processed in 0.425072 second(s), 84 queries .

    回顶部