迪杰斯特拉(Dijkstra)算法

haige

带权图的最短路径问题的matlab函数代码
function y = shortest_path(i,j)
, z) C0 q* n% S8 `( Da=load('A.mat');
+ _" N; Z7 o- m) j) y- XA=a.a;
N = length(A);                                   t
S = zeros(1,N);                                 
( `! ]8 T6 c! H4 qS(1) = i;                                       
( x) f5 e" p. y+ y0 T8 c; r4 q7 ?6 sdist = A(i,;                                   
8 C% K: O. R5 ]; h: ]9 L  g" b, r6 ?flag = 0;                                       
5 w; I& R$ c! a" [: V4 X+ T; Z& @8 l% Hcount = 1;                                       
while (flag~=1)
    [value,position] = min(dist);               
+ a7 Q2 L2 z' A, t( ]# A    dist(i) = inf;                              
    if (position == j)
1 G; q+ z% U* T7 C. M' \        flag = 1;
9 _9 \! |7 \- W8 u" v1 ]' v    else
        count = count + 1;
        S(count) = position;
0 C- S  _' [+ }: z+ J" t        for o = 1:N
3 A/ O9 h* e- Y, r. R( X            dist(o) = min(dist(o),dist(position)+A(position,o));
3 W  S; E( ]$ |7 P! O! S. o( u, O        end
7 Z& m& \' |9 j$ _8 z        dist(position) = inf;                    % point can't back to itself,so weight = inf
    end
end
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.