迪杰斯特拉(Dijkstra)算法

haige

带权图的最短路径问题的matlab函数代码
function y = shortest_path(i,j)
a=load('A.mat');
0 L0 j# W# J; \' k! C" t. oA=a.a;
N = length(A);                                   t
S = zeros(1,N);                                 
S(1) = i;                                       
. E$ M( |3 C- e, E# Y9 K: i9 vdist = A(i,;                                   
% c* y2 M/ J, I; D2 P- @: Jflag = 0;                                       
count = 1;                                       
3 k8 W& b" N7 A% o3 a! I& \while (flag~=1)
    [value,position] = min(dist);               
    dist(i) = inf;                              
! F0 r9 x. Z8 }: n, D3 A    if (position == j)
' Y4 t/ X  L. F8 d& u8 p* l% O$ c* h        flag = 1;
) b1 e1 _+ h( [9 R+ ^& V( o    else
        count = count + 1;
: Q+ T9 O6 i. M        S(count) = position;
# ^" ^; v. @0 n7 b% y. e        for o = 1:N
) z! R4 I1 @) K& u# J            dist(o) = min(dist(o),dist(position)+A(position,o));
        end
& U: s1 }" L, D" |: g" m        dist(position) = inf;                    % point can't back to itself,so weight = inf
* P) r) [" u5 k/ T, b    end
end
: z: T$ [! t9 t& Z+ \y = 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.