数学建模社区-数学中国
标题:
关于dijkstra的问题。
[打印本页]
作者:
晒个小太阳。
时间:
2013-1-19 22:42
标题:
关于dijkstra的问题。
我手头有一个现成的dijkstra算法的matlab程序，但是只能输出某个点到最短通路的值，以及标号顶点顺序，以及标号顶点索引。
- }* n5 s8 [" R5 Q7 q4 k; Q
7 ? _$ W; p y! {! a9 S, x
3 h# [: N$ ^8 K; }, C8 I$ Q+ A& ]# ^
我想知道有没有什么程序能够输出具体的最短路径，比如说从1到5的最短路径是1->3->4->5，就是类似这样的，有没有这样的dijkstra程度啊。 如果没有的话，那通过现有的是不是能推出来呢？望高人指点啊~小弟感激不尽。
K) Y! O1 z' I6 G; P* E
- L8 U* S# I! ]& e+ M/ q. y8 _8 D9 o
对了，我还想问最短路径生成树是什么东西？？
- k; B+ T& w, c4 r0 \9 l" f
0 ]8 d% H9 C4 s4 g
附程序如下：
3 W, Z$ H4 A8 a* ]8 T
clear;
) O' r; Q6 P% V. J: ?
clc;
C% ^8 o# Y; w+ Q. U% a( s
M=10000;
. Z/ O' f" l; E% N
a(1,:)=[0,50,M,40,25,10];
K, l, V- x' Y4 w- m
a(2,:)=[zeros(1,2),15,20,M,25];
: w. s% [! p/ X! L7 n7 ]
a(3,:)=[zeros(1,3),10,20,M];
1 h/ Y8 o% x& W) X2 w2 }, @7 ^
a(4,:)=[zeros(1,4),10,25];
* r& t' }* l- W, b1 s: r& |4 U. \5 ?" u
a(5,:)=[zeros(1,5),55];
- I" n% V. a$ h7 D. V8 J7 [6 R
a(6,:)=zeros(1,6);
# `- G7 u% |" @ K% R; K9 F
a=a+a';
& M8 R+ S: T, }2 p# x. n2 O: x) J9 c2 I
pb(1:length(a))=0;pb(1)=1;index1=1;index2=ones(1,length(a));
8 j( o9 k- ^7 G9 @2 i+ R9 e* I8 D
d(1:length(a))=M;d(1)=0;temp=1;
; @8 M% a+ b% p& G9 Z
while sum(pb)<length(a)
7 P7 ^* c$ I" M; v2 V
tb=find(pb==0);
# Z' s0 v" u% |2 u
d(tb)=min(d(tb),d(temp)+a(temp,tb));
- c7 ]$ Y/ v. `9 ?
tmpb=find(d(tb)==min(d(tb)));
) A l3 F# }' C/ w& _: [& B
temp=tb(tmpb(1));
8 J$ Q5 r* d* G1 `) j$ t
pb(temp)=1;
7 N& R& F# {) O4 l0 p, L6 U7 A
index1=[index1,temp];
7 ?9 N0 Q& b6 S! b* {, _$ K9 Y; }
index=index1(find(d(index1)==d(temp)-a(temp,index1)));
4 K6 e: a* i* z) P
if length(index)>=2
( T) k- g2 N: \1 y& r& K1 f
index=index(1);
4 k, A1 o: O! D4 D% B' j2 C
end
) B( Q0 G& b+ `. }3 w" }
index2(temp)=index;
7 O3 e7 @5 G+ J/ w ]+ x6 ?
end
! y# R! e* v ~$ f
d, index1, index2
8 b8 R5 N# u" i" n( N% D! T
作者:
木兆木风
时间:
2013-1-20 09:36
我这里有VC2008的，需要的话我可以给你发
作者:
和谐宁静
时间:
2013-8-22 18:50
用LINGo挺好的 对于这个算法
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5