迪杰斯特拉(Dijkstra)算法

haige

带权图的最短路径问题的matlab函数代码
# M) h: V8 D, A, k. Vfunction y = shortest_path(i,j)
a=load('A.mat');
4 v9 B: x4 f' rA=a.a;
# y; e/ [& Y: b) R' C. xN = length(A);                                   t
S = zeros(1,N);                                 
S(1) = i;                                       
dist = A(i,;                                   
flag = 0;                                       
count = 1;                                       
7 r* q. H$ \/ B, }5 z. Pwhile (flag~=1)
" o" Q  n8 M3 u4 R1 X$ E    [value,position] = min(dist);               
    dist(i) = inf;                              
    if (position == j)
        flag = 1;
( a- k% e/ b. h! b    else
4 X9 A( y/ I1 ?- i% s4 t# s        count = count + 1;
        S(count) = position;
6 U& P) ?( F' p6 x) k1 ]        for o = 1:N
            dist(o) = min(dist(o),dist(position)+A(position,o));
        end
+ A. S5 m8 Y& V% ]; \* Z. J        dist(position) = inf;                    % point can't back to itself,so weight = inf
; ?1 ^8 T) d9 A- W9 U; c# R: ]    end
end
7 E& m( |& D  Ey = value;

fantimond

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.