迪杰斯特拉(Dijkstra)算法

haige

带权图的最短路径问题的matlab函数代码
, T& r4 _% T0 Dfunction y = shortest_path(i,j)
1 j& P$ O& O5 A. q4 _5 I1 Za=load('A.mat');
A=a.a;
N = length(A);                                   t
& y# v+ y' ]5 S  ]; S6 x9 m) ZS = zeros(1,N);                                 
+ @/ z6 |, H& oS(1) = i;                                       
dist = A(i,;                                   
, e8 z( @8 i, @5 Uflag = 0;                                       
count = 1;                                       
while (flag~=1)
    [value,position] = min(dist);               
    dist(i) = inf;                              
    if (position == j)
8 ?' D5 V" R, A1 X4 z, I        flag = 1;
# }: S% \- _1 [  K) p2 `  u    else
        count = count + 1;
        S(count) = position;
        for o = 1:N
            dist(o) = min(dist(o),dist(position)+A(position,o));
. A9 C. M: I, y3 i: k        end
        dist(position) = inf;                    % point can't back to itself,so weight = inf
- f" R& |- o$ d    end
! p; |" d- _' Xend
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.