迪杰斯特拉(Dijkstra)算法

haige

带权图的最短路径问题的matlab函数代码
function y = shortest_path(i,j)
a=load('A.mat');
A=a.a;
N = length(A);                                   t
& L8 x. C$ e4 `/ B3 L( uS = zeros(1,N);                                 
S(1) = i;                                       
dist = A(i,;                                   
flag = 0;                                       
count = 1;                                       
0 A6 a* N$ S- ?1 jwhile (flag~=1)
    [value,position] = min(dist);               
$ ?% q$ s7 S6 |, M9 C. z    dist(i) = inf;                              
+ K3 z3 \1 Y+ F  {0 e, V6 e1 S$ r    if (position == j)
        flag = 1;
- I" L0 H' Q6 ^3 B4 M    else
2 d. L' @, X) q2 U        count = count + 1;
) \' u" u7 Z; b        S(count) = position;
2 c& s; O. c) Y, |0 [, g- U        for o = 1:N
; e4 E, l1 L, m" V, B            dist(o) = min(dist(o),dist(position)+A(position,o));
        end
        dist(position) = inf;                    % point can't back to itself,so weight = inf
" f5 ^! q8 ~4 ?$ J$ {' W( X- X    end
4 A( O9 L3 `, M+ U& a& vend
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.