QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 4426|回复: 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程序。。。。。但是有些看不懂啊~~~那个大神指教一下~~~~
    8 N7 _, w  I9 m# T4 A
    ; f( R+ _3 G: B9 GFloyd算法函数在matlab下的M函数文件如下:& o+ U, H/ o6 n* ^( K
    function [D,path]=floyd(a)
    4 [- v) q1 G" e; a8 |n=size(a,1);" P& x- [8 Y/ o0 _
    D=a;path=zeros(n,n);
      E- Z! d: u1 X4 Jfor i=1:n
    - U: ]% f: D0 r) n, d/ d  u    for j=1:n
    ( k9 t, \0 N; z' M        if D(i,j)~=inf
    ' D( ]) B: @8 \* C7 F; i& {            path(i,j)=j;
    - l  d% U, r* d8 b2 _6 l9 p, E        end
      ^  e% G' k" g3 I1 h    end
    5 `+ ~# j1 {: `- t* s. p3 z  h8 `! _end
    8 x/ Z* Q0 `; y# ~5 @7 L$ h7 g7 jfor k=1:n
    5 K; T6 B8 H1 n/ P' V) i- a    for i=1:n+ g! o- P" |% ?+ {
            for j=1:n* g: Z6 Y% B. A- C- O& r
                if D(i,k)+D(k,j)<D(i,j)) o* o; h: }. d4 x( R. }
                    D(i,j)=D(i,k)+D(k,j);
    , ^% i$ }7 J/ p' e& i5 S" g; i                path(i,j)=path(i,k);3 }2 ^1 u" b8 l# }6 z4 N& b
                end
    * _0 Z9 K' k2 E% }        end
    7 o# Z# {; s1 Z( T" a    end
    . e+ q' Z* y  m0 |: i2 Z' ?end
    1 r9 A" k0 h0 b$ h/ [6 Y上面是一个函数,这一部分可以看懂,但是下面这个求最小费的问题就看不懂了。。。。
    # K. Q! x' b: U5 Tab=[1 1 2 3 4 5 6 7 8 9 10 11 12 13 15 16 17 18 19 20  20 22 23];7 p, x8 H! }! A- n- q! |
    bb=[ 14 15 15 16 19 18 23 24 10 10 11 15 13 14 16 17 19 19 20 21 22 23 24];
    % e3 w2 X/ P% Y1 j5 Vw=[20 202 1200 690  690 462 70 30 450 80 1150 1100 306 195 720 520 170 88 160 70 320 160 290];. w9 Y' x' b7 @3 Y& ?* t9 v
    ab1=[1 2 4 5 6 7 8 9 10 11 14 15 16 17 18 33 34 35];+ {! u" h& s; e: w4 m" N  @; }, i
    bb1=[19 20 21 22 23 24 25 26 27 28 29 30 31 31 19 24 31 32];
    ( y& W9 r+ h% \3 J6 o+ |+ ]w1=[3 2 600 10 5 10 12 42 70 10 10 62 30 20  104 31 110 20];
    # L* v( c5 `4 l+ o( q0 i; T) a# e9 Ma=sparse(ab,bb,w);
    1 D' M! |; R4 Q1 Ya(24,24)=0;, ]) t4 W" o1 h8 U
    a=a+a’;! \  b7 e, r4 S+ C; s0 ^
    a=full(a);
    # L- [! X$ B% i" {) ~6 w( Q% @, Yfor i=1:24, Y+ v+ s: ?  D' O( M8 m7 g2 X' V
        for j=1:24& o, |4 K& f# G9 S5 ]- e
            if(a(i,j)==0&i~=j)
    / S6 P. V  n( _2 }9 Q. [# g            a(i,j)=inf;7 `9 U$ K$ Q' H* |8 F- |
            end+ u9 U5 |( L8 i$ h9 O9 p( d- t
        end4 s& a/ j5 Q+ \
    end; q! A% K% f! Y/ g
    [D,path]=floyd(a);4 {2 Z2 H& G: ?7 ?, x$ a7 V' F
    a1=sparse(ab1,bb1,w1);
    6 }6 _( ]( l, M( k. ~$ oa1(35,35)=0;  {) |0 S; S, I1 I2 h( \/ @
    a1=a1+(a1)';$ H: W- N( a+ ^4 I! g* T8 E
    a1=full(a1);
    5 M7 h. ]# u  d( z) V; M# F; \for i=1:35+ h0 e/ i2 |9 Y- y. n
        for j=1:35" D/ c4 W2 l7 O. b" H# ~  o- T; v
            if(a1(i,j)==0&i~=j)
    . Q# O) R6 g6 w+ x/ T2 [* [) `            a1(i,j)=inf;/ E; ?1 v1 O* p, f  G' g
            end6 o" j: u/ @/ E1 A# Q
        end6 g  Y8 k4 {5 }/ y
    end2 k8 w) _, G% `4 D6 b; X
    [D1,path1]=floyd(a1);
    9 |4 m7 w3 }5 J上面这一段应该是赋值求最短路了吧,,,但是这赋值是赋得什么值额????有大神的话可以在后面注释一下。。。万分感谢。。。
    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题)8 \# N) R1 n& y; x" o9 p4 T
         要铺设一条的输送天然气的主管道,如图所示。经筛选后可以生产这种主管道钢管的钢厂有。图中粗线表示铁路,单细线表示公路,双线表示要铺设的管道(假设沿管道或者原有公路,或者建有施工公路),圆圈(点) 表示火车站,' U* f+ A1 R: V, ~" d4 [$ V
      每段铁路、公路和管道旁的阿拉伯数字表示里程(单位km)。
    2 q1 e/ D" y) w- R* ~       为方便计,1km主管道钢管称为1单位钢管。
    ) w8 p& Z1 @  c. S: U) a7 M4 E    一个钢厂如果承担制造这种钢管,至少需要生产500个单位。钢厂在指定期限内能生产该钢管的最大数量为个单位,钢管出厂销价1单位钢管为万元,如下表:- @( E  W8 P# |0 \8 c5 U
    I           1           2           3          4          5          6           7
    # ~7 Z- J) M+ F: e3 d  C5 o        800        800        1000        2000        2000        2000        3000
    5 p/ L* U# P3 H* [7 {5 e. m8 P        160        155        155        160        155        150        160
    " `1 _8 [! r  I: K" w; V  一单位钢管的铁路运价如下表:2 t5 [: ^% T* q
    里程(km)        ≤300        301~350        351~400        401~450        451~500
    / ]0 ]2 U  Z5 d- |运价(万元)        20        23        26        29        32
    $ c& x5 E7 _2 e! p里程(km)        501~600        601~700        701~800        801~900        901~1000$ ^; g7 O6 ~9 O2 N" C1 ^% m
    运价(万元)        37        44        50        55        60
    8 x; }& G8 U- a# t/ K  1000km以上每增加1至100km运价增加5万元。& V: {; [) w) X; v6 t
         公路运输费用为1单位钢管每公里0·1万元(不足整公里部分按整公里计算)。+ r5 z. m5 `# t' |' Q
      钢管可由铁路、公路运往铺设地点(不只是运到点,而是管道全线)。
    : E$ Z# v/ k0 b5 x请制定一个主管道钢管的订购和运输计划,使总费用最小(给出总费用)。- X1 e: e4 [" x& w, x' x: v7 H
    请就(1)的模型分析:哪个钢厂钢管的销价的变化对购运计划和总费用影响最大,哪个钢厂钢管的产量的上限的变化对购运计划和总费用的影响最大,并给出相应的数字结果。
    ( k( ?0 s9 u2 B5 f如果要铺设的管道不是一条线,而是一个树形图,铁路、公路和管道构成网络,请就这种更一般的情况给出一种解决办法,并对图二按(1)的要求给出模型和结果.
    " a; P/ t# u+ k7 h$ u1 o0 T2 X2 p
    ) D. \7 l' p$ l1 o* BC:\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题)) W$ Q2 Q' A& S# y- Y8 |9 k: X0 A
         要铺设一条的输送天然气的主管道,如图所示。经筛选后可以生产这种主管道钢管的钢厂有。图中粗线表示铁路,单细线表示公路,双线表示要铺设的管道(假设沿管道或者原有公路,或者建有施工公路),圆圈(点) 表示火车站,; `2 J% `. Y( P, T  _" A; j% q
      每段铁路、公路和管道旁的阿拉伯数字表示里程(单位km)。$ L" _7 y, L0 {& N, q- M
           为方便计,1km主管道钢管称为1单位钢管。
    . ?1 q+ @; Z# R/ G1 b* \1 Q' Z    一个钢厂如果承担制造这种钢管,至少需要生产500个单位。钢厂在指定期限内能生产该钢管的最大数量为个单位,钢管出厂销价1单位钢管为万元,如下表:  L1 w) ?5 J- u) d* |
    I           1           2           3          4          5          6           7
    & A4 _( |: l1 K" e6 r& w. f2 XSi        800        800        1000        2000        2000        2000        3000
    3 n4 I) n& k. i$ i' R+ @2 H1 @- s  \& ZPi        160        155        155        160        155        150        1600 B9 m8 k% I; f4 V
      一单位钢管的铁路运价如下表:3 |! Q# W7 U. n1 V5 y& v
    里程(km)        ≤300        301~350        351~400        401~450        451~5001 N' ]8 t6 _! V( R% d3 l9 P& w
    运价(万元)        20        23        26        29        32
    + W) X. _/ w9 E里程(km)        501~600        601~700        701~800        801~900        901~1000
    ; u: o, n" f: _# ^运价(万元)        37        44        50        55        60
    / x3 M" ?( @) e1 M( n1 R- @  1000km以上每增加1至100km运价增加5万元。6 ^6 r% ]  }3 o1 l8 x
         公路运输费用为1单位钢管每公里0·1万元(不足整公里部分按整公里计算)。
    2 R* ~& t- E/ [) ?, _( H4 A  钢管可由铁路、公路运往铺设地点(不只是运到点,而是管道全线)。- h7 V$ Z6 g) U0 C; c; G+ y1 R
    1.请制定一个主管道钢管的订购和运输计划,使总费用最小(给出总费用)。& v8 p, f* l% q/ f/ }( q  V0 _/ d
    2.请就(1)的模型分析:哪个钢厂钢管的销价的变化对购运计划和总费用影响最大,哪个钢厂钢管的产量的上限的变化对购运计划和总费用的影响最大,并给出相应的数字结果。8 i, L% V/ I( M% H. F' f
    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-10 02:23 , Processed in 3.459041 second(s), 86 queries .

    回顶部