迪杰斯特拉(Dijkstra)算法

haige

带权图的最短路径问题的matlab函数代码
4 P9 H7 b" j9 vfunction y = shortest_path(i,j)
4 R( D5 O; t7 B9 m4 p' Ma=load('A.mat');
A=a.a;
N = length(A);                                   t
& y. Z+ o, g+ g, l4 Q- M" ^S = zeros(1,N);                                 
S(1) = i;                                       
dist = A(i,;                                   
flag = 0;                                       
' M& f% ~5 `- J( Z1 rcount = 1;                                       
% }" @/ {% ^4 x! `while (flag~=1)
    [value,position] = min(dist);               
    dist(i) = inf;                              
    if (position == j)
. }4 }& P* A2 q        flag = 1;
    else
1 ^  Q& Z& V! i( r5 h        count = count + 1;
        S(count) = position;
; v1 u- O! M( P3 M8 u3 [# P3 e        for o = 1:N
            dist(o) = min(dist(o),dist(position)+A(position,o));
        end
6 X1 }) d# U! T        dist(position) = inf;                    % point can't back to itself,so weight = inf
    end
end
7 K2 Q1 A2 ]* m; |3 O" l( Y4 Fy = 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.