数学建模社区-数学中国
标题:
关于dijkstra的问题。
[打印本页]
作者:
晒个小太阳。
时间:
2013-1-19 22:42
标题:
关于dijkstra的问题。
我手头有一个现成的dijkstra算法的matlab程序，但是只能输出某个点到最短通路的值，以及标号顶点顺序，以及标号顶点索引。
; B) A" u+ S& m8 v3 T! z* J R4 H" y
! Y$ G6 ?/ S4 a! ~, B9 q0 \% ~2 [
7 I! F6 y8 S8 z' ?7 H
我想知道有没有什么程序能够输出具体的最短路径，比如说从1到5的最短路径是1->3->4->5，就是类似这样的，有没有这样的dijkstra程度啊。 如果没有的话，那通过现有的是不是能推出来呢？望高人指点啊~小弟感激不尽。
( O/ u- Q# R3 `& w* Y8 |
8 D1 N) z/ M0 s
对了，我还想问最短路径生成树是什么东西？？
* o7 ]$ I& v; v0 z8 ~
8 l5 b/ u1 Z$ o2 L' d* |7 q7 u! |1 ^
附程序如下：
. R' h" A& s( W2 K; M ]: v
clear;
& {* D- n2 M& \& g' j$ x2 k
clc;
$ ?8 |9 h$ J/ q2 u! {
M=10000;
+ a* h# a( o% g' z- [) T ]
a(1,:)=[0,50,M,40,25,10];
/ ~% X, Z+ T. E4 o) |: ~
a(2,:)=[zeros(1,2),15,20,M,25];
: D P8 X6 n) p% _+ m- \
a(3,:)=[zeros(1,3),10,20,M];
3 Y' R* E- D5 [ k% b2 f
a(4,:)=[zeros(1,4),10,25];
# D7 c* y! ~ Y5 C. N0 b
a(5,:)=[zeros(1,5),55];
6 T( ^) k7 x. _* X9 y
a(6,:)=zeros(1,6);
: w3 X4 `5 V5 X: ?" A4 T! k/ w* b
a=a+a';
0 {: s6 q8 j4 p1 ^; A9 T7 h
pb(1:length(a))=0;pb(1)=1;index1=1;index2=ones(1,length(a));
- ?/ W9 d! w8 b/ B$ a8 ^
d(1:length(a))=M;d(1)=0;temp=1;
! V4 ]5 f. u: B3 r! H. `7 r2 C2 b
while sum(pb)<length(a)
) X. Q3 ^" T# Z) h
tb=find(pb==0);
0 r0 w( b: Z: \) {
d(tb)=min(d(tb),d(temp)+a(temp,tb));
3 m1 j6 E; x) O) L4 O# t& K4 d
tmpb=find(d(tb)==min(d(tb)));
; J) ~, t) |8 M, N, h
temp=tb(tmpb(1));
1 C' h X, U8 @. M3 [% H( t
pb(temp)=1;
+ T& ~0 \6 B: a; y( r( N. k" P
index1=[index1,temp];
8 ~7 o' g p) {9 d
index=index1(find(d(index1)==d(temp)-a(temp,index1)));
4 H' @- i; x" n$ I
if length(index)>=2
6 i$ V7 a d3 _3 K
index=index(1);
# V( h3 a" m, Z
end
5 C/ O& V, ]5 v1 X. ?; Z
index2(temp)=index;
1 g2 g+ T4 W$ w* F
end
- n- I0 j. j( N ^$ P2 V U+ i
d, index1, index2
' p; t# K# ^/ Q" `' u2 A/ A0 H
作者:
木兆木风
时间:
2013-1-20 09:36
我这里有VC2008的，需要的话我可以给你发
作者:
和谐宁静
时间:
2013-8-22 18:50
用LINGo挺好的 对于这个算法
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5