数学建模社区-数学中国
标题:
关于dijkstra的问题。
[打印本页]
作者:
晒个小太阳。
时间:
2013-1-19 22:42
标题:
关于dijkstra的问题。
我手头有一个现成的dijkstra算法的matlab程序，但是只能输出某个点到最短通路的值，以及标号顶点顺序，以及标号顶点索引。
0 @; G0 u0 T2 l4 _; _
- ]4 B# Y$ C3 E8 J% l
]1 x7 W7 r' e9 @
我想知道有没有什么程序能够输出具体的最短路径，比如说从1到5的最短路径是1->3->4->5，就是类似这样的，有没有这样的dijkstra程度啊。 如果没有的话，那通过现有的是不是能推出来呢？望高人指点啊~小弟感激不尽。
8 g/ Y$ V4 `* W) C7 Y; ^& {. S
- x! _9 R. c7 O M0 {) U/ s
对了，我还想问最短路径生成树是什么东西？？
/ h" K% i; X; v: l
; R& O% v& b. y8 I s! A1 i' l. f4 r
附程序如下：
" ?& H9 d% Q# Y2 A9 y2 r9 b5 a
clear;
$ V% `' S' P2 g' D% _; v7 C
clc;
3 Q3 M) T/ L" ]7 I0 E( w# H
M=10000;
, a( T a% i# b3 ^( H, B/ j
a(1,:)=[0,50,M,40,25,10];
6 @+ o$ q/ v2 I
a(2,:)=[zeros(1,2),15,20,M,25];
% G6 `1 i+ C+ }
a(3,:)=[zeros(1,3),10,20,M];
0 m/ T1 C; u; k, J9 p+ l
a(4,:)=[zeros(1,4),10,25];
: b+ o6 w7 X; J, y* y% K
a(5,:)=[zeros(1,5),55];
, m8 K# p" x. E/ G, u; T( d Z \8 Y" M
a(6,:)=zeros(1,6);
2 W& p" d& X3 o0 M
a=a+a';
6 v3 V# i0 E# k$ x7 @- O; p
pb(1:length(a))=0;pb(1)=1;index1=1;index2=ones(1,length(a));
$ b( L+ W, A8 {
d(1:length(a))=M;d(1)=0;temp=1;
4 _. \( F1 |* h0 x; t: a
while sum(pb)<length(a)
8 D+ }! p/ z4 z- d
tb=find(pb==0);
; X3 ]9 d0 H/ B: m
d(tb)=min(d(tb),d(temp)+a(temp,tb));
/ Q- A- R, K! ?; @0 z7 o4 E
tmpb=find(d(tb)==min(d(tb)));
! ]' ?& Q- A# ^
temp=tb(tmpb(1));
% d3 Q4 b+ R9 t$ {0 Z( g0 \
pb(temp)=1;
/ B+ i1 h/ B3 Y$ ^+ h0 a+ K
index1=[index1,temp];
0 H/ T3 u* f( ?
index=index1(find(d(index1)==d(temp)-a(temp,index1)));
3 K# r% F/ e3 F9 _1 Q( u
if length(index)>=2
( {% G5 l, e' e& s
index=index(1);
- S% p6 `7 q' Y: M! q$ W Q7 g
end
) H% |1 K( V9 J' N6 g
index2(temp)=index;
' a- j$ D1 r( R( c
end
2 n5 p$ T: N3 t: L
d, index1, index2
$ T% _( t+ s$ b/ L. v! _6 Q
作者:
木兆木风
时间:
2013-1-20 09:36
我这里有VC2008的，需要的话我可以给你发
作者:
和谐宁静
时间:
2013-8-22 18:50
用LINGo挺好的 对于这个算法
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5