迪杰斯特拉(Dijkstra)算法

haige

带权图的最短路径问题的matlab函数代码
" N) H+ I6 `9 x0 b* Wfunction y = shortest_path(i,j)
a=load('A.mat');
# K# y  Z( e: s. jA=a.a;
7 C6 s" y" D( H( YN = length(A);                                   t
S = zeros(1,N);                                 
S(1) = i;                                       
dist = A(i,;                                   
6 L  v$ q5 k* z2 tflag = 0;                                       
6 L5 s2 y) Q9 ], Q% e# Icount = 1;                                       
while (flag~=1)
    [value,position] = min(dist);               
7 R# g6 j! k2 m. r( C5 V    dist(i) = inf;                              
0 t- Q0 D, F* I' y1 ^6 o# p, i- {    if (position == j)
        flag = 1;
    else
        count = count + 1;
        S(count) = position;
        for o = 1:N
  d7 D: V% d) x3 V& A            dist(o) = min(dist(o),dist(position)+A(position,o));
- \9 m0 a" F$ z, n        end
) ^4 d9 ^- p$ I( A' ^+ _2 T( r* P+ w" E        dist(position) = inf;                    % point can't back to itself,so weight = inf
" }6 G/ e; p1 D+ U9 ^# x    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.