标题: 迪杰斯特拉(Dijkstra)算法 [打印本页] 作者: haige 时间: 2009-5-23 14:23 标题: 迪杰斯特拉(Dijkstra)算法 带权图的最短路径问题的matlab函数代码4 Z5 N2 [2 {$ Y! c+ M/ _
function y = shortest_path(i,j) . D* e" R0 h. Z3 I5 Qa=load('A.mat');3 B G9 G) |) N2 U: i9 O4 C
A=a.a; * ~' n/ O0 c& RN = length(A); t8 R: k; }$ J, Y5 x4 e, i' p
S = zeros(1,N); 2 E, @7 D' J% y: x
S(1) = i; 7 I/ P0 _% c c5 w+ i9 h0 Odist = A(i,; D' v/ j; i2 J9 C" ]! k' `
flag = 0; 6 i2 [ G9 p! t- o4 u1 K8 vcount = 1; % v) H2 u8 U7 \; \$ ~3 o- a
while (flag~=1) ! M' Z6 M9 ~/ e$ ~4 L [value,position] = min(dist); 5 ]0 v5 Z2 T% I% P( `8 `
dist(i) = inf; # f2 c9 H( l: j if (position == j) 9 s% c: \ K" _7 O% c6 n flag = 1;. H$ m) N1 [ a6 ?& ~7 k
else Y$ W1 Z4 }; ?3 a, o8 ]# E9 T
count = count + 1;- m- o' r6 x; R& k
S(count) = position; 0 |/ o2 R9 r1 n4 q2 K8 I0 a for o = 1:N5 j" N8 v7 B# r; E
dist(o) = min(dist(o),dist(position)+A(position,o)); % L; j, t/ r( @+ l2 t end - e( H$ h0 O+ k- N* W dist(position) = inf; % point can't back to itself,so weight = inf% Y# m; O+ Q' u/ R& u$ b0 k
end: `3 {7 U2 o. B
end $ m$ K2 ^& ?! z' ^# |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.
; D' v/ j; i2 J9 C" ]! k' `