迪杰斯特拉(Dijkstra)算法

haige

带权图的最短路径问题的matlab函数代码
function y = shortest_path(i,j)
; N  V/ q% s  _- M( |1 a+ Na=load('A.mat');
A=a.a;
N = length(A);                                   t
) C9 w& [+ o& ^7 i/ rS = zeros(1,N);                                 
S(1) = i;                                       
9 G8 c' i7 @( b# p! rdist = A(i,;                                   
flag = 0;                                       
; D. N0 U( r0 L* \) Y% Pcount = 1;                                       
1 g% E/ |: ~) Ywhile (flag~=1)
* ?1 x( _" g! R    [value,position] = min(dist);               
    dist(i) = inf;                              
    if (position == j)
1 d9 A( G/ g7 \        flag = 1;
/ g: \4 i! D' H7 q0 V    else
        count = count + 1;
3 B' G! ~' _' o6 [        S(count) = position;
" e% z9 o6 F1 T& U        for o = 1:N
8 c; h, e: M1 B4 @            dist(o) = min(dist(o),dist(position)+A(position,o));
        end
; |' c) r- [) B5 z- y4 _0 ^1 m# T        dist(position) = inf;                    % point can't back to itself,so weight = inf
6 E- b% V, C4 Y6 ]    end
end
. d0 e. f0 A9 dy = 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.