QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 4428|回复: 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程序。。。。。但是有些看不懂啊~~~那个大神指教一下~~~~( S8 u- C" L" U% Y2 ^

    & x0 M% i" j5 _' r8 s6 t( dFloyd算法函数在matlab下的M函数文件如下:8 O" ~' [9 y$ |( a) C8 {
    function [D,path]=floyd(a)
    ; C% o/ }: O, N! x1 d4 Z8 Qn=size(a,1);- n0 E) C* M; y" U
    D=a;path=zeros(n,n);& V; L" ^- j* O6 B) Z, M" j) Y
    for i=1:n7 K* ~  h8 m' \. |
        for j=1:n
    ' {3 I- S0 p4 ^' G) _  y        if D(i,j)~=inf8 b' }( |- x' y  U
                path(i,j)=j;
    - {) M' z, s9 q4 m: Y& f6 W& F        end
    " ^( r' m" l) |! T, b( y. @  ~3 ~    end, R2 y, g7 ~3 m! d+ \+ j" C( M. T3 ]: e
    end; Z* n# @) {  f4 y+ H& {
    for k=1:n* g& i% ?/ q' ^& Y9 M
        for i=1:n( J! j7 u/ m+ S2 D" T
            for j=1:n
    " N- \1 t5 d8 w; p. B* T            if D(i,k)+D(k,j)<D(i,j)
    " W% c+ J2 \6 M) K" c: W                D(i,j)=D(i,k)+D(k,j);
    8 r4 R; T% Y; a                path(i,j)=path(i,k);* D( C$ i( M& \9 _
                end
    6 L8 y, {/ e. I9 x) e        end
    6 \9 ^0 B; j4 h8 |( d    end. `# @" y2 x% F, _6 D! c3 L
    end$ M4 ]6 g* o8 l; C6 Y, D5 L( m
    上面是一个函数,这一部分可以看懂,但是下面这个求最小费的问题就看不懂了。。。。
    # ^/ Y$ q# s) S& W1 T! |! E+ mab=[1 1 2 3 4 5 6 7 8 9 10 11 12 13 15 16 17 18 19 20  20 22 23];- z2 F3 A( b( k. B
    bb=[ 14 15 15 16 19 18 23 24 10 10 11 15 13 14 16 17 19 19 20 21 22 23 24];
    0 V" T+ k9 F, T% ew=[20 202 1200 690  690 462 70 30 450 80 1150 1100 306 195 720 520 170 88 160 70 320 160 290];0 u5 O- S- D9 {0 D
    ab1=[1 2 4 5 6 7 8 9 10 11 14 15 16 17 18 33 34 35];' |3 F9 l, p! H# n7 a' b
    bb1=[19 20 21 22 23 24 25 26 27 28 29 30 31 31 19 24 31 32];; T. u8 C# Z, K' |7 o0 r% V( T
    w1=[3 2 600 10 5 10 12 42 70 10 10 62 30 20  104 31 110 20];
    ; _. L( K0 S% ]& W2 y; ~2 Ha=sparse(ab,bb,w);
    0 K" A% x8 {5 Fa(24,24)=0;
    : E# Z0 z. |& d- D( Ca=a+a’;# J6 x6 q- N1 R( T+ q" V, |
    a=full(a);+ E, K3 _; K3 Z/ C) b5 E
    for i=1:24
    * x' D+ n0 z) }- P    for j=1:24" k. x$ [% X* i" m$ V/ F
            if(a(i,j)==0&i~=j)( m$ P/ H3 H) X, @
                a(i,j)=inf;
    % p, U5 k( S" ^. j  m' k  [* h7 y. Y        end
    & [1 F2 L) z; D    end
    % k4 u  ~( j. P! d) c6 Tend* R2 J" R* g  M) I
    [D,path]=floyd(a);
    1 v& G3 k# ~' V6 X8 qa1=sparse(ab1,bb1,w1);
    9 v: P( ]( }1 w" S" s, ea1(35,35)=0;
    6 H$ L5 f$ I! Xa1=a1+(a1)';4 X' }3 [* r8 w/ j6 w; P' x* H
    a1=full(a1);$ K2 @# j8 Y7 h4 r# o+ h$ U% S
    for i=1:35, s  z) U. P; B7 r, I% W* d0 _5 N
        for j=1:35
      x! r. b( I- S, R        if(a1(i,j)==0&i~=j)/ |. ?$ X6 A0 k
                a1(i,j)=inf;
    5 A! U* e3 r6 @9 T  s+ F( d        end3 I! K4 U) l; o5 m9 a1 L
        end
    . u; Q7 X0 _( w4 u) a3 @$ @end
    9 x, K0 H/ \# o[D1,path1]=floyd(a1);+ k8 H6 r, Q, e4 _- |+ u) i# t
    上面这一段应该是赋值求最短路了吧,,,但是这赋值是赋得什么值额????有大神的话可以在后面注释一下。。。万分感谢。。。
    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题)
    - B1 N$ ^) _9 G2 K/ s4 m' G7 p     要铺设一条的输送天然气的主管道,如图所示。经筛选后可以生产这种主管道钢管的钢厂有。图中粗线表示铁路,单细线表示公路,双线表示要铺设的管道(假设沿管道或者原有公路,或者建有施工公路),圆圈(点) 表示火车站,; E6 v2 u7 Z# S3 Z
      每段铁路、公路和管道旁的阿拉伯数字表示里程(单位km)。) B1 j0 i- w: ?) T, t
           为方便计,1km主管道钢管称为1单位钢管。- r& z8 [! [; p% a% S: n
        一个钢厂如果承担制造这种钢管,至少需要生产500个单位。钢厂在指定期限内能生产该钢管的最大数量为个单位,钢管出厂销价1单位钢管为万元,如下表:
    8 v, i3 n" C' p- b. Z2 KI           1           2           3          4          5          6           7; |$ }$ L$ J5 F6 F' }& b$ Y
            800        800        1000        2000        2000        2000        30007 W( J. c% j' x3 A- f
            160        155        155        160        155        150        160
    3 h! T  C+ b: B, y  一单位钢管的铁路运价如下表:
    : c. t  l% b) z1 U0 X  ]. ^$ T/ j里程(km)        ≤300        301~350        351~400        401~450        451~500
    ; P& ]6 v. o9 j* ]- ]( ?运价(万元)        20        23        26        29        32
    6 E4 h  x9 B  {  b' G% q里程(km)        501~600        601~700        701~800        801~900        901~1000: u1 g4 z3 @6 l4 K, y% L
    运价(万元)        37        44        50        55        60: B. m/ k9 H- {5 G2 F- Y" [2 s
      1000km以上每增加1至100km运价增加5万元。7 l  t) ?( F! M" b
         公路运输费用为1单位钢管每公里0·1万元(不足整公里部分按整公里计算)。
    0 W$ Y; u, _% [( t! g8 ^( u3 p  钢管可由铁路、公路运往铺设地点(不只是运到点,而是管道全线)。3 h, q! k( E3 r/ r$ p5 u
    请制定一个主管道钢管的订购和运输计划,使总费用最小(给出总费用)。3 q& x1 J* ~8 W9 V3 e
    请就(1)的模型分析:哪个钢厂钢管的销价的变化对购运计划和总费用影响最大,哪个钢厂钢管的产量的上限的变化对购运计划和总费用的影响最大,并给出相应的数字结果。
    0 l' w- U1 h/ {如果要铺设的管道不是一条线,而是一个树形图,铁路、公路和管道构成网络,请就这种更一般的情况给出一种解决办法,并对图二按(1)的要求给出模型和结果.
    " j/ H& K% Q& P2 p
    ) c3 ?3 e. O, K+ |# SC:\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题)
    % M+ G* ~9 s  L9 e/ n     要铺设一条的输送天然气的主管道,如图所示。经筛选后可以生产这种主管道钢管的钢厂有。图中粗线表示铁路,单细线表示公路,双线表示要铺设的管道(假设沿管道或者原有公路,或者建有施工公路),圆圈(点) 表示火车站,
    2 h9 o+ L2 M; g$ [* s+ L  每段铁路、公路和管道旁的阿拉伯数字表示里程(单位km)。
    3 E. c% ~3 |  e5 D) F6 O       为方便计,1km主管道钢管称为1单位钢管。! Q1 j( b- N0 a: ~1 q" z6 ]) }
        一个钢厂如果承担制造这种钢管,至少需要生产500个单位。钢厂在指定期限内能生产该钢管的最大数量为个单位,钢管出厂销价1单位钢管为万元,如下表:
    ' X' l# ~' s- T7 b2 KI           1           2           3          4          5          6           74 t; n2 q+ X+ W
    Si        800        800        1000        2000        2000        2000        30004 j; g& J5 E8 k
    Pi        160        155        155        160        155        150        160
      x( Z& J) R6 r& M) W% s+ b  一单位钢管的铁路运价如下表:4 k% a% s1 j8 g3 ~* U3 `. e
    里程(km)        ≤300        301~350        351~400        401~450        451~500
    7 u0 u" }. C1 b; [7 z2 Y5 X运价(万元)        20        23        26        29        32
    # G0 X+ C7 y% r# u; Z里程(km)        501~600        601~700        701~800        801~900        901~10001 ^' o4 k6 N5 H# w4 Y( B/ R
    运价(万元)        37        44        50        55        60
    % i& `+ |* ^. w, ]  1000km以上每增加1至100km运价增加5万元。7 r6 c- n, C$ S% [2 z0 q1 T
         公路运输费用为1单位钢管每公里0·1万元(不足整公里部分按整公里计算)。
    5 x8 e( a$ ]& a2 r9 v7 y5 |, i  Y  钢管可由铁路、公路运往铺设地点(不只是运到点,而是管道全线)。
    / I, o2 T. h4 ~9 p; U1 B# F& R1.请制定一个主管道钢管的订购和运输计划,使总费用最小(给出总费用)。
    8 a; [! A7 T: T) \; d) o2.请就(1)的模型分析:哪个钢厂钢管的销价的变化对购运计划和总费用影响最大,哪个钢厂钢管的产量的上限的变化对购运计划和总费用的影响最大,并给出相应的数字结果。
    $ e8 {; [8 x) ~/ X3.如果要铺设的管道不是一条线,而是一个树形图,铁路、公路和管道构成网络,请就这种更一般的情况给出一种解决办法,并对图二按(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-11 02:03 , Processed in 0.546389 second(s), 85 queries .

    回顶部