数学建模社区-数学中国
标题:
迪杰斯特拉(Dijkstra)算法
[打印本页]
作者:
haige
时间:
2009-5-23 14:23
标题:
迪杰斯特拉(Dijkstra)算法
带权图的最短路径问题的matlab函数代码
+ o( a0 o/ ?8 c% [4 G- O
function y = shortest_path(i,j)
+ p- e9 w$ Y3 ]' j5 u- ~5 @
a=load('A.mat');
! R* w. F) K" ~3 v
A=a.a;
6 J# g& o0 ]0 t. p6 W) i
N = length(A); t
3 Y. T. T( C' H9 q6 K g ?6 ?, ?
S = zeros(1,N);
) z7 \9 q5 W/ h ] ?% Q
S(1) = i;
1 m/ u) }; N0 \% x
dist = A(i,
;
4 f0 O* ? \8 t' u$ B7 L; h, W2 }
flag = 0;
/ t* Z$ ?8 Z9 h/ M2 V
count = 1;
- n. S6 o6 i! o4 p- t3 g& u$ w4 u" @; Y
while (flag~=1)
, k& ]1 l2 x! g: E8 j
[value,position] = min(dist);
; V5 [% D" |/ a" M& a* b# q
dist(i) = inf;
0 v0 K+ [1 _) L1 e
if (position == j)
1 G6 j3 `) `9 d' m/ M! Z9 k
flag = 1;
- |# E: y* T+ f/ Q" ~3 o$ P
else
1 O6 b/ ?1 ^. _ D; K1 e; E
count = count + 1;
0 F7 I& J" z8 X9 @1 _ a$ V& i( I
S(count) = position;
7 s$ z8 n, K4 R: g/ l' ?. J& z
for o = 1:N
) l0 J4 E; W' Z( q! E! p
dist(o) = min(dist(o),dist(position)+A(position,o));
3 @% E& T4 r3 y' Z
end
& J7 v2 K# ~* B; Y0 _) d6 H
dist(position) = inf; % point can't back to itself,so weight = inf
$ M% U( b& e4 p3 v
end
9 e& M* }# N ]( y/ i
end
5 _& Z2 }6 N6 d" I
y = value;
作者:
fantimond
时间:
2009-5-25 15:58
This Algorithm is designed to get one available shortest path vertex at every step.Then when it ends, it gave the shortest path value of every vertex from the source.
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5
;