- 在线时间
- 30 小时
- 最后登录
- 2014-2-8
- 注册时间
- 2012-11-24
- 听众数
- 7
- 收听数
- 0
- 能力
- 0 分
- 体力
- 334 点
- 威望
- 0 点
- 阅读权限
- 30
- 积分
- 140
- 相册
- 0
- 日志
- 0
- 记录
- 0
- 帖子
- 94
- 主题
- 6
- 精华
- 0
- 分享
- 0
- 好友
- 18
升级   20% TA的每日心情 | 郁闷 2014-2-7 13:28 |
|---|
签到天数: 47 天 [LV.5]常住居民I
- 自我介绍
- 好好学习,天天向上。
 |
我手头有一个现成的dijkstra算法的matlab程序,但是只能输出某个点到最短通路的值,以及标号顶点顺序,以及标号顶点索引。
2 Q- r" L7 J" F r& Z* H/ Z3 a! r( N( o) g, H# J0 g# y3 b$ F
) a% ?5 D- j5 h3 s, q+ A我想知道有没有什么程序能够输出具体的最短路径,比如说从1到5的最短路径是1->3->4->5,就是类似这样的,有没有这样的dijkstra程度啊。 如果没有的话,那通过现有的是不是能推出来呢?望高人指点啊~小弟感激不尽。& j7 u/ e5 W s* W
7 g: ^- Y, Q0 |& n) I. w3 z6 a
对了,我还想问最短路径生成树是什么东西??1 G* N, T' l# }+ S# e8 w7 u0 R/ T& X( Q
/ Y6 z0 l; ^9 D
附程序如下:) F* y. M# G9 V7 [2 W
clear;/ i& C' A$ x7 T# R. M: x
clc;# C) D4 k( X; j
M=10000;& m/ B7 y* x2 y& H" w! }
a(1,:)=[0,50,M,40,25,10];
) K/ N( A1 {) N7 C) ]2 F, Q; x- Va(2,:)=[zeros(1,2),15,20,M,25];4 e4 w4 G1 L5 F# _4 q7 S
a(3,:)=[zeros(1,3),10,20,M];
- u q1 t& N c8 Ia(4,:)=[zeros(1,4),10,25];3 k" z. x0 K/ m) Q# @4 ~
a(5,:)=[zeros(1,5),55];
# B1 W! {. a$ D5 ua(6,:)=zeros(1,6);- ~- ]# `$ K/ t% c7 s
a=a+a';. t+ W, \6 w1 _ _: J, A
pb(1:length(a))=0;pb(1)=1;index1=1;index2=ones(1,length(a));
& a9 a! d5 N/ Q: M9 w7 c6 Y( Id(1:length(a))=M;d(1)=0;temp=1;
. ^ q; P0 m* A- i7 C$ Fwhile sum(pb)<length(a)
% M; J* ^/ N4 Y, Z& ~ tb=find(pb==0);
6 K8 g8 ^/ @! R! m d(tb)=min(d(tb),d(temp)+a(temp,tb));" F0 Q ]' `9 ~( R% m' l
tmpb=find(d(tb)==min(d(tb)));7 I8 ^+ Q. x* L3 o2 n) F
temp=tb(tmpb(1));+ Q v7 y* z& l- R6 \
pb(temp)=1;
' z7 g/ n6 f5 F5 N+ u$ G5 n6 [ index1=[index1,temp];
X* G- C. U8 Q$ g) c0 ]% B index=index1(find(d(index1)==d(temp)-a(temp,index1)));) C: j3 S* T- j) Y0 F- M
if length(index)>=21 X; H; s) _1 x2 p
index=index(1);9 T+ p( K3 }( F' F
end, t5 g4 r; O" m1 |7 ?% v
index2(temp)=index;
* Z6 k6 z' R2 s: l8 dend
3 n5 f( g( p5 e+ q$ x4 _% `* y e8 Xd, index1, index2 / m" ?$ H2 g0 X/ j! s
|
zan
|