迪杰斯特拉(Dijkstra)算法

haige

带权图的最短路径问题的matlab函数代码
- m: @  N2 W- j" q! ofunction y = shortest_path(i,j)
$ j  a( |6 X" S1 R7 {0 E  T( ya=load('A.mat');
% U! V' S/ G# `+ i' K3 c$ |, [7 c  |A=a.a;
3 Z/ [: o3 J! k+ b( Q. VN = length(A);                                   t
S = zeros(1,N);                                 
S(1) = i;                                       
1 g% y/ J9 Y2 m& mdist = A(i,;                                   
* ]/ B5 ], j/ L( w3 nflag = 0;                                       
; J. d4 k  ]# c1 g; Jcount = 1;                                       
while (flag~=1)
) a. n0 l" J+ ~2 c& w    [value,position] = min(dist);               
, Z: I4 w- @( ~' t, Y! z: b+ j    dist(i) = inf;                              
1 J4 E/ I" F9 p% m    if (position == j)
        flag = 1;
0 O4 ^+ {+ L  j' [# n7 E0 K    else
        count = count + 1;
        S(count) = position;
5 {- s8 a5 K: W% C; E& m, L8 f        for o = 1:N
            dist(o) = min(dist(o),dist(position)+A(position,o));
' l7 R% e6 e0 N( j# I        end
; p" `( ], p3 o1 V/ X$ ^* `! H! h        dist(position) = inf;                    % point can't back to itself,so weight = inf
0 K' M5 Q  S. o8 b' C! r: D1 M8 Y    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.