迪杰斯特拉(Dijkstra)算法

haige

带权图的最短路径问题的matlab函数代码
0 T+ C0 V' d  v6 }  Q3 y; |function y = shortest_path(i,j)
5 w6 r9 ^: C8 f/ l1 h3 [' v: ha=load('A.mat');
' f' V( V/ P0 g8 y6 IA=a.a;
N = length(A);                                   t
/ w/ v0 V( _; HS = zeros(1,N);                                 
5 l* g9 `9 s6 |. `. ?6 {S(1) = i;                                       
dist = A(i,;                                   
flag = 0;                                       
count = 1;                                       
while (flag~=1)
    [value,position] = min(dist);               
    dist(i) = inf;                              
9 @6 d: h4 U5 Y" P9 }7 H    if (position == j)
        flag = 1;
    else
# R1 ^3 N* J4 ]7 [        count = count + 1;
        S(count) = position;
        for o = 1:N
; `  [4 S8 v/ a3 z+ e+ u8 o) R            dist(o) = min(dist(o),dist(position)+A(position,o));
2 S! C( _, u4 X        end
0 q6 S1 ?# Y* p& ?! S9 r        dist(position) = inf;                    % point can't back to itself,so weight = inf
    end
end
9 P1 n# }5 V' P5 v- l* Uy = 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.