- 在线时间
- 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程序,但是只能输出某个点到最短通路的值,以及标号顶点顺序,以及标号顶点索引。
( a$ J$ m2 L7 U1 E, h3 J) H% |& z* Q; H8 D
8 ?: m+ \/ `* z
我想知道有没有什么程序能够输出具体的最短路径,比如说从1到5的最短路径是1->3->4->5,就是类似这样的,有没有这样的dijkstra程度啊。 如果没有的话,那通过现有的是不是能推出来呢?望高人指点啊~小弟感激不尽。
" h0 t/ N/ {7 Z+ `: f" {$ b5 ~
1 _: W6 W8 s5 Q9 b" }* H对了,我还想问最短路径生成树是什么东西??
6 k" l1 a- B5 s$ p* |# a7 D* z$ ]# V) f4 _5 D$ n, }9 [: [
附程序如下:
4 `( N' K3 t/ @% H0 ~clear;
7 [7 s z) t# c, ^& Q" Sclc;
7 N0 e4 H0 _% }3 p+ mM=10000;4 A p8 w( j! ^
a(1,:)=[0,50,M,40,25,10];& F; {3 B' k2 s+ ]8 D& ~# }2 q
a(2,:)=[zeros(1,2),15,20,M,25];/ k$ o6 X, J# L! q# J" u. B
a(3,:)=[zeros(1,3),10,20,M];4 N) d; i& ~4 E; L
a(4,:)=[zeros(1,4),10,25];; X/ j, \, o {6 H2 A! i0 W
a(5,:)=[zeros(1,5),55];* {2 q% K& r, y2 D/ T* u
a(6,:)=zeros(1,6);
% O! d$ m. d; X1 z5 T) x& J' Ha=a+a';
& Z# B) m; C/ o6 a A3 lpb(1:length(a))=0;pb(1)=1;index1=1;index2=ones(1,length(a));- m2 H$ ]0 w; a4 u
d(1:length(a))=M;d(1)=0;temp=1;) W$ K7 N7 T4 J, h
while sum(pb)<length(a)
4 F) I6 C0 g6 S/ i: u tb=find(pb==0);
! v8 e9 Y3 j# B3 q/ g8 m3 Z d(tb)=min(d(tb),d(temp)+a(temp,tb));) [7 @& w# ~( o4 S+ }8 H( J- O0 [& c
tmpb=find(d(tb)==min(d(tb)));( g! x! S% o7 C$ S" _
temp=tb(tmpb(1));
& q8 z; r, v" w pb(temp)=1;, [; Q: Q4 L; }- Y7 |3 L
index1=[index1,temp];/ Y+ H$ g- _2 r# X1 D: v+ d. M
index=index1(find(d(index1)==d(temp)-a(temp,index1)));
- A7 U5 x* j" K, e1 D7 d, F. l if length(index)>=27 K/ m9 t% Q$ N' I9 {" _# |; W
index=index(1);
) D5 a& Y! n) D! J8 a3 ~/ X end: {) ?. K" m9 U/ f% B
index2(temp)=index;
- J5 V8 K; P3 pend
9 l' B, U) w& V* w- M# K* s9 ^) td, index1, index2
& c2 X/ c. e9 f5 Y |
zan
|