迪杰斯特拉(Dijkstra)算法

haige

带权图的最短路径问题的matlab函数代码
function y = shortest_path(i,j)
a=load('A.mat');
A=a.a;
3 @5 Q1 R4 Y4 x' L! K$ JN = length(A);                                   t
- g- L3 l2 t( @# H* HS = zeros(1,N);                                 
5 k+ t1 l, d" g- N4 e/ VS(1) = i;                                       
" u3 `# v3 v: c$ Jdist = A(i,;                                   
. {. }9 O7 e; @. U  y- t  nflag = 0;                                       
7 ~# y% u! D' c' c- U4 R: ecount = 1;                                       
while (flag~=1)
    [value,position] = min(dist);               
, c9 M# B; z* g7 z0 U( e9 Z! I    dist(i) = inf;                              
) M% B  w) g: h6 B) H    if (position == j)
+ _. ^7 t2 q/ R9 A9 C        flag = 1;
& ?# K/ q' w9 ?. X) A    else
        count = count + 1;
1 i; E- C0 U5 j; R0 A8 Y: U        S(count) = position;
, k1 G* H5 |2 K$ ?  K8 J3 l& V3 \        for o = 1:N
            dist(o) = min(dist(o),dist(position)+A(position,o));
        end
        dist(position) = inf;                    % point can't back to itself,so weight = inf
    end
end
4 @9 X. f. e) I' Ay = 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.