迪杰斯特拉(Dijkstra)算法

haige

带权图的最短路径问题的matlab函数代码
function y = shortest_path(i,j)
: ]% a# V% R% d9 }0 p* M" Ba=load('A.mat');
A=a.a;
( S; z9 {. a/ X$ t8 nN = length(A);                                   t
S = zeros(1,N);                                 
3 r* Y$ Y' y6 d0 X9 E1 KS(1) = i;                                       
! w2 `& c2 e$ ]dist = A(i,;                                   
flag = 0;                                       
5 ^- `3 C2 e0 ^. q0 |) rcount = 1;                                       
- M  W9 V5 C+ Y7 y' `while (flag~=1)
    [value,position] = min(dist);               
. z& t3 T7 I  `4 U    dist(i) = inf;                              
7 u" j2 L! @3 u; v    if (position == j)
+ u( b* w3 X7 z        flag = 1;
    else
        count = count + 1;
/ @% f/ u! ^9 b* U+ d5 ~, v        S(count) = position;
& J" W" u/ ?% M! X; L+ N        for o = 1:N
            dist(o) = min(dist(o),dist(position)+A(position,o));
+ J- i( z" O% G- B% [3 W: j        end
        dist(position) = inf;                    % point can't back to itself,so weight = inf
    end
) G7 Y7 g1 }! }/ [5 j  ~/ aend
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.