数学建模社区-数学中国

标题: 关于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 Tclear;
) O' r; Q6 P% V. J: ?clc;
  C% ^8 o# Y; w+ Q. U% a( sM=10000;. Z/ O' f" l; E% N
a(1,:)=[0,50,M,40,25,10];
  K, l, V- x' Y4 w- ma(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 Ra(6,:)=zeros(1,6);
# `- G7 u% |" @  K% R; K9 Fa=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