数学建模社区-数学中国
标题:
关于dijkstra的问题。
[打印本页]
作者:
晒个小太阳。
时间:
2013-1-19 22:42
标题:
关于dijkstra的问题。
我手头有一个现成的dijkstra算法的matlab程序，但是只能输出某个点到最短通路的值，以及标号顶点顺序，以及标号顶点索引。
2 _, j; T9 X7 c( O6 ]& v( |: U
8 P6 }5 x6 }% P; ?) t! A
0 h0 A1 J/ w, W$ l
我想知道有没有什么程序能够输出具体的最短路径，比如说从1到5的最短路径是1->3->4->5，就是类似这样的，有没有这样的dijkstra程度啊。 如果没有的话，那通过现有的是不是能推出来呢？望高人指点啊~小弟感激不尽。
3 `" d4 }8 i- \1 F3 t) B% P
1 V8 [) O# ]* `( Q/ k
对了，我还想问最短路径生成树是什么东西？？
7 B& n3 [* f" ?: F( w7 A+ G% H$ F
4 X1 P) k! J# K( l0 o& J9 J9 Z/ F
附程序如下：
/ F) z2 k" z. h" S% q
clear;
8 o: ]) x1 V" S- k
clc;
@5 k/ N8 F O9 \& O5 s. b
M=10000;
1 c7 [6 f! b+ v l# f
a(1,:)=[0,50,M,40,25,10];
8 v0 W( a) h% u3 M: h5 K
a(2,:)=[zeros(1,2),15,20,M,25];
. e$ Y& i( W0 t$ k' J5 |; @6 R& C8 y
a(3,:)=[zeros(1,3),10,20,M];
3 g A: q; _4 z6 y
a(4,:)=[zeros(1,4),10,25];
1 d. A/ M( o b
a(5,:)=[zeros(1,5),55];
5 v9 w1 X' o7 U% g
a(6,:)=zeros(1,6);
) W6 u7 A8 c8 }1 R, n4 D7 Q5 g
a=a+a';
4 b/ a w, o0 F, w& r
pb(1:length(a))=0;pb(1)=1;index1=1;index2=ones(1,length(a));
3 T, b+ O# t! v7 j$ J% b/ n, o8 h
d(1:length(a))=M;d(1)=0;temp=1;
% ?1 p; A3 L3 Q6 t
while sum(pb)<length(a)
& |7 O6 H6 u' w# V6 P3 N* k
tb=find(pb==0);
1 l% Y6 R- u( c
d(tb)=min(d(tb),d(temp)+a(temp,tb));
+ \7 E, i9 G* N, [
tmpb=find(d(tb)==min(d(tb)));
5 [7 j) Y) ^& z2 G* O
temp=tb(tmpb(1));
& t; g, J: b) S* ^, g( u, G
pb(temp)=1;
, V2 ?: Y/ X" y$ c" u R! W
index1=[index1,temp];
: W3 @* \0 j# W
index=index1(find(d(index1)==d(temp)-a(temp,index1)));
3 x5 B1 g' w7 R6 G5 ]5 r# ]* `
if length(index)>=2
& a3 v: g. o$ f9 J5 b8 P
index=index(1);
, L8 f6 Z s0 f7 \! {
end
; z5 z7 _$ }$ x5 s+ H
index2(temp)=index;
+ \! d" m: Z( ?6 C
end
9 j0 A o- G/ D* h
d, index1, index2
. r: k% ?# N& D6 X+ {2 p
作者:
木兆木风
时间:
2013-1-20 09:36
我这里有VC2008的，需要的话我可以给你发
作者:
和谐宁静
时间:
2013-8-22 18:50
用LINGo挺好的 对于这个算法
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5