数学建模社区-数学中国
标题:
关于dijkstra的问题。
[打印本页]
作者:
晒个小太阳。
时间:
2013-1-19 22:42
标题:
关于dijkstra的问题。
我手头有一个现成的dijkstra算法的matlab程序，但是只能输出某个点到最短通路的值，以及标号顶点顺序，以及标号顶点索引。
% V; Q3 m% P' k6 a. p
$ s9 e2 K$ Y8 i# `- Z# e
6 S5 c6 b) d" m) Q
我想知道有没有什么程序能够输出具体的最短路径，比如说从1到5的最短路径是1->3->4->5，就是类似这样的，有没有这样的dijkstra程度啊。 如果没有的话，那通过现有的是不是能推出来呢？望高人指点啊~小弟感激不尽。
( N, M. B$ D) I: O. ?
1 O! S% ~$ v' t% a" q9 o
对了，我还想问最短路径生成树是什么东西？？
* ]2 t: |9 o k; G1 {. Q6 }
1 |: n9 B) F D
附程序如下：
% ^- W& f) s1 a5 L& @' E
clear;
! v5 q) j, H+ W+ b8 N
clc;
$ p' P! f3 t C0 v$ S: }; x
M=10000;
8 [; p. A1 A8 T% c. m4 T, ?
a(1,:)=[0,50,M,40,25,10];
# f4 [% f; }/ V k) T# ^
a(2,:)=[zeros(1,2),15,20,M,25];
( T2 H$ K+ a& A# x( s; H
a(3,:)=[zeros(1,3),10,20,M];
, c: A* j' o1 j! D5 ?1 @8 b! L
a(4,:)=[zeros(1,4),10,25];
9 D0 N* f' o; t! r3 O/ i2 c
a(5,:)=[zeros(1,5),55];
8 v% a9 x7 y: m4 \' M
a(6,:)=zeros(1,6);
5 w7 k$ }' V! }) I% L& R; i3 X
a=a+a';
+ w; m- V, a M0 @ @" H) p r
pb(1:length(a))=0;pb(1)=1;index1=1;index2=ones(1,length(a));
8 d! G0 l; t0 H! W: S+ b* ?: S, L
d(1:length(a))=M;d(1)=0;temp=1;
3 F4 d3 J2 R6 o: j
while sum(pb)<length(a)
, o* w" n( ]" o9 j& y
tb=find(pb==0);
' I- A1 }4 y, {3 X6 @5 a
d(tb)=min(d(tb),d(temp)+a(temp,tb));
( ]! |# d4 ?2 _
tmpb=find(d(tb)==min(d(tb)));
% j$ p6 M% y# U8 e7 ^ C
temp=tb(tmpb(1));
- f3 L7 O+ f- w' I \+ K
pb(temp)=1;
: I' H7 x: K) H2 g) X+ M
index1=[index1,temp];
; `2 g |$ E8 H, T. W
index=index1(find(d(index1)==d(temp)-a(temp,index1)));
. m- D, U; L" T: [/ c
if length(index)>=2
. M) r- R8 Z! c/ Q% c U6 j8 c
index=index(1);
5 Q7 t% w1 g2 h* @2 t) g
end
" N" |0 F4 W' G7 V' b y$ B4 r
index2(temp)=index;
p" y5 u F& K/ k N
end
0 }- B3 F# q! x' j# x
d, index1, index2
9 }! W# e+ b& J/ U5 v* m
作者:
木兆木风
时间:
2013-1-20 09:36
我这里有VC2008的，需要的话我可以给你发
作者:
和谐宁静
时间:
2013-8-22 18:50
用LINGo挺好的 对于这个算法
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5