迪杰斯特拉(Dijkstra)算法

haige

带权图的最短路径问题的matlab函数代码
function y = shortest_path(i,j)
" k) O9 \: O# A4 t+ V5 T& {5 Ha=load('A.mat');
A=a.a;
N = length(A);                                   t
. X6 e/ `9 V0 I1 m6 \S = zeros(1,N);                                 
S(1) = i;                                       
, }/ F; U- x8 M+ u$ n9 o3 ydist = A(i,;                                   
flag = 0;                                       
count = 1;                                       
. o5 H# W8 ^1 wwhile (flag~=1)
- |/ @; D, e' g/ }    [value,position] = min(dist);               
    dist(i) = inf;                              
( p( J# u0 q5 n1 a    if (position == j)
  X3 c- q1 M  z" A7 Y        flag = 1;
    else
        count = count + 1;
        S(count) = position;
        for o = 1:N
            dist(o) = min(dist(o),dist(position)+A(position,o));
) Q$ h; _1 m' |& D        end
        dist(position) = inf;                    % point can't back to itself,so weight = inf
7 F% {3 |! s0 f# q    end
% [3 Y3 o6 t" K1 j) n2 Jend
4 K! U5 |) F/ n2 B' k& ]+ z! jy = 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.