迪杰斯特拉(Dijkstra)算法

haige

带权图的最短路径问题的matlab函数代码
+ o8 u4 p( j4 ~- Q7 h- T4 }. Wfunction y = shortest_path(i,j)
a=load('A.mat');
A=a.a;
, ]6 D% R$ {- [# I) \N = length(A);                                   t
- Y" y, Q% N( P5 F+ c9 A$ n) n1 XS = zeros(1,N);                                 
1 ]/ |( s; z9 p' `7 K5 k9 sS(1) = i;                                       
7 _( @# j) a% ^/ a" t( \dist = A(i,;                                   
4 t$ {3 n8 U( u/ cflag = 0;                                       
6 z# _7 r. @; X5 i+ g: }count = 1;                                       
while (flag~=1)
    [value,position] = min(dist);               
    dist(i) = inf;                              
    if (position == j)
: X# |5 r+ q& B" B& p% s8 j        flag = 1;
    else
        count = count + 1;
        S(count) = position;
" \  [& h; m. h. D' p  d        for o = 1:N
            dist(o) = min(dist(o),dist(position)+A(position,o));
8 v( W9 ^2 ^9 b$ B        end
        dist(position) = inf;                    % point can't back to itself,so weight = inf
    end
# F# l" X: S4 o# W0 d% M& Y' Nend
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.