迪杰斯特拉(Dijkstra)算法

haige

带权图的最短路径问题的matlab函数代码
# @0 Y4 v9 q- M8 I  ?; N0 g* [function y = shortest_path(i,j)
a=load('A.mat');
+ L' w; @3 b+ I5 ~0 N& vA=a.a;
' N6 V& f$ v9 F  l' [N = length(A);                                   t
S = zeros(1,N);                                 
( {" I/ M- ]/ \2 [  xS(1) = i;                                       
0 [  M  _" }  |dist = A(i,;                                   
flag = 0;                                       
count = 1;                                       
- q9 b& H) ~4 q  ~while (flag~=1)
    [value,position] = min(dist);               
    dist(i) = inf;                              
3 W  x3 p/ `) `% j+ ~% ^- t# V    if (position == j)
        flag = 1;
    else
1 c. j8 h$ b5 G4 U) s# Z2 T        count = count + 1;
        S(count) = position;
        for o = 1:N
( x, B0 E: d6 J- u; W# e0 o            dist(o) = min(dist(o),dist(position)+A(position,o));
0 D2 |: N& e' W, W& X        end
        dist(position) = inf;                    % point can't back to itself,so weight = inf
. j5 t' c) B' z5 f5 K3 f    end
6 C9 X! Q# P; v0 @. B& tend
' q, s& W  h4 |& A- Q- p1 a$ Sy = 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.