迪杰斯特拉(Dijkstra)算法

haige

带权图的最短路径问题的matlab函数代码
function y = shortest_path(i,j)
a=load('A.mat');
A=a.a;
N = length(A);                                   t
S = zeros(1,N);                                 
S(1) = i;                                       
dist = A(i,;                                   
flag = 0;                                       
+ u+ A1 V6 B9 ~+ {count = 1;                                       
/ q7 j' d" }3 v$ H: p7 E- @% T8 t. qwhile (flag~=1)
1 Z; r. g3 |7 Q; H6 Y    [value,position] = min(dist);               
    dist(i) = inf;                              
    if (position == j)
        flag = 1;
    else
        count = count + 1;
7 J2 B- N5 W0 q7 @        S(count) = position;
        for o = 1:N
            dist(o) = min(dist(o),dist(position)+A(position,o));
        end
8 t- o; P, S  H0 j. P% w/ N        dist(position) = inf;                    % point can't back to itself,so weight = inf
    end
: ?6 l4 }  |/ f8 l/ _end
  F. ?9 B7 r% K' x7 G+ Z+ h( ry = 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.