迪杰斯特拉(Dijkstra)算法

haige

带权图的最短路径问题的matlab函数代码
! v) v1 a6 Z3 ~function y = shortest_path(i,j)
8 n9 f1 f/ J, v& J1 ^% V% c3 Ia=load('A.mat');
A=a.a;
N = length(A);                                   t
S = zeros(1,N);                                 
S(1) = i;                                       
dist = A(i,;                                   
3 _& T) s$ g, `3 }, [$ r, zflag = 0;                                       
2 C% L3 z& l- ^count = 1;                                       
while (flag~=1)
. ]# S" u* F  S    [value,position] = min(dist);               
$ k6 k5 w) a  j) \    dist(i) = inf;                              
9 T: w% n& H5 {5 Y2 Z    if (position == j)
/ |: \0 |; Y5 F0 k1 u% Z: X2 ?: I' O        flag = 1;
    else
; \  v. L! ?+ e+ W8 [4 k( r        count = count + 1;
        S(count) = position;
7 K. I, Q$ Q7 j* n2 ^4 S3 h        for o = 1:N
            dist(o) = min(dist(o),dist(position)+A(position,o));
        end
        dist(position) = inf;                    % point can't back to itself,so weight = inf
4 S+ i0 @+ n6 U& k2 M% {    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.