迪杰斯特拉(Dijkstra)算法

haige

带权图的最短路径问题的matlab函数代码
- m$ J+ |0 v5 p$ ?0 Ifunction y = shortest_path(i,j)
( |- \) U+ o7 b% o( sa=load('A.mat');
A=a.a;
N = length(A);                                   t
; S& B$ m: N" D5 F0 T$ t' M% CS = zeros(1,N);                                 
S(1) = i;                                       
dist = A(i,;                                   
flag = 0;                                       
6 {( E0 I# I% k4 ccount = 1;                                       
while (flag~=1)
    [value,position] = min(dist);               
    dist(i) = inf;                              
$ k9 e( ^$ e/ L# z0 C2 R    if (position == j)
        flag = 1;
. U1 g3 \" H4 _1 o- P    else
9 Y& ~9 f' l/ q2 Q. P, j        count = count + 1;
* G. u- h' `( D7 m( A5 `5 A. ?; G        S(count) = position;
        for o = 1:N
1 U, k: z3 `) @' L            dist(o) = min(dist(o),dist(position)+A(position,o));
        end
/ j2 M; B1 q" P% B" B) D        dist(position) = inf;                    % point can't back to itself,so weight = inf
' w% t6 F8 g% w3 f) q- x$ o' U    end
/ t/ r% x+ E( iend
) A# H6 L7 F4 k( `) {% Ly = 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.