QQ登录

只需要一步,快速开始

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

[问题求助] 关于dijkstra的问题。

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

6

主题

7

听众

140

积分

升级  20%

  • TA的每日心情
    郁闷
    2014-2-7 13:28
  • 签到天数: 47 天

    [LV.5]常住居民I

    自我介绍
    好好学习,天天向上。
    跳转到指定楼层
    1#
    发表于 2013-1-19 22:42 |只看该作者 |倒序浏览
    |招呼Ta 关注Ta
    我手头有一个现成的dijkstra算法的matlab程序,但是只能输出某个点到最短通路的值,以及标号顶点顺序,以及标号顶点索引。
    3 |4 I$ E* t1 l) t) ?
      J* ^, g' m3 A3 U6 o8 o, i0 c8 r) I& [4 j
    我想知道有没有什么程序能够输出具体的最短路径,比如说从1到5的最短路径是1->3->4->5,就是类似这样的,有没有这样的dijkstra程度啊。  如果没有的话,那通过现有的是不是能推出来呢?望高人指点啊~小弟感激不尽。
    5 _( E  U+ I3 Q1 n% l  Y, _- F6 Z6 J$ N% ^
    对了,我还想问最短路径生成树是什么东西??, h; r5 ^* u) j, h& `
    : P' r# g4 T- _
    附程序如下:
    " P4 O- H& w% E: Jclear;
    : j' L- {5 _( o, {7 a/ ^# C% L0 C" Aclc;+ }, L6 |+ g  }0 |) U5 O( o
    M=10000;
    0 i4 D( x  X, _$ b: Ja(1,:)=[0,50,M,40,25,10];
    1 t% {/ y) O2 ]: |a(2,:)=[zeros(1,2),15,20,M,25];% k$ p& Q* F* y0 q
    a(3,:)=[zeros(1,3),10,20,M];" G  m$ Z- Y0 x2 R
    a(4,:)=[zeros(1,4),10,25];
    5 T  F# ^3 Q2 |9 |& s: b# s0 Qa(5,:)=[zeros(1,5),55];1 v& I0 \- G+ M$ g/ f
    a(6,:)=zeros(1,6);
    ' E% W$ O" y: @7 Oa=a+a';4 u( T6 R) H/ ~  |" P
    pb(1:length(a))=0;pb(1)=1;index1=1;index2=ones(1,length(a));
    8 Z9 J$ s  j# P. yd(1:length(a))=M;d(1)=0;temp=1;
    $ \  x- P" |+ {+ W/ O) U' |while sum(pb)<length(a)
    ! |: D* I# u: O+ H# B   tb=find(pb==0);7 f, K$ ~; H2 J! h% \/ k
       d(tb)=min(d(tb),d(temp)+a(temp,tb));
    - k# a7 c& G3 s* _/ f   tmpb=find(d(tb)==min(d(tb)));! W+ V0 u! L9 C+ N7 H# M
       temp=tb(tmpb(1));0 C* j$ \" V5 V  `5 l
       pb(temp)=1;9 U9 x2 x" K  @& ]9 e! i9 o
       index1=[index1,temp];$ ~- O9 v# Z" I* d1 }
       index=index1(find(d(index1)==d(temp)-a(temp,index1)));
    . W0 X& ~: q' \5 S   if length(index)>=27 M' D% m2 E6 R0 S
          index=index(1);  K! {( ?! |/ i2 u2 A) z$ p& P$ T' ^
       end( v6 v7 K7 w% B' X8 b4 r
       index2(temp)=index;- `4 E5 w& ^6 y  O4 h! e
    end
    1 Z: }9 N8 T$ P  V0 [d, index1, index2 $ v" P$ I9 w- q
    zan
    转播转播0 分享淘帖0 分享分享0 收藏收藏0 支持支持0 反对反对0 微信微信

    2

    主题

    13

    听众

    311

    积分

    升级  3.67%

  • TA的每日心情
    奋斗
    2015-6-16 11:06
  • 签到天数: 9 天

    [LV.3]偶尔看看II

    自我介绍
    我是一名数学爱好者

    社区QQ达人

    群组英语科技论文写作实训

    群组2017国赛赛前最后冲刺

    群组2016国赛护航基础强化

    群组2017美赛护航基础强化

    群组2018乐考无忧考研数学

    回复

    使用道具 举报

    19

    主题

    11

    听众

    488

    积分

    升级  62.67%

  • TA的每日心情
    开心
    2014-10-22 22:24
  • 签到天数: 192 天

    [LV.7]常住居民III

    自我介绍
    热爱数学

    群组2013认证赛D题讨论群组

    群组Matlab讨论组

    群组数学建摸协会

    群组第四届数学中国美赛实

    回复

    使用道具 举报

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

    qq
    收缩
    • 电话咨询

    • 04714969085
    fastpost

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

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

    蒙公网安备 15010502000194号

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

    GMT+8, 2026-6-6 18:54 , Processed in 0.420928 second(s), 68 queries .

    回顶部