迪杰斯特拉(Dijkstra)算法

haige

带权图的最短路径问题的matlab函数代码
function y = shortest_path(i,j)
% x. [" q! F1 W6 @9 `a=load('A.mat');
A=a.a;
* J. G* a4 K7 c7 vN = length(A);                                   t
S = zeros(1,N);                                 
, @7 o6 q$ s# K9 h7 nS(1) = i;                                       
( B# w# P8 l  d7 |dist = A(i,;                                   
$ G7 M8 N9 x9 T( P+ E4 uflag = 0;                                       
count = 1;                                       
) T# d) G, ]$ e5 |while (flag~=1)
, {2 L1 ?) e, w" U" u8 u3 \+ p    [value,position] = min(dist);               
  r" M9 K6 ]/ t0 ~$ u/ g6 J    dist(i) = inf;                              
. B# }- F# |2 I    if (position == j)
7 }, q) q7 V( i        flag = 1;
    else
' f6 P( U0 |8 C6 `; }        count = count + 1;
& P: o- E0 [; d4 b& {/ J4 U  Q1 T9 H' R        S(count) = position;
4 z- p7 s+ X' o+ I+ Z% t        for o = 1:N
            dist(o) = min(dist(o),dist(position)+A(position,o));
        end
5 b  l" g1 `& t& p* u        dist(position) = inf;                    % point can't back to itself,so weight = inf
/ C/ M' _1 j6 O+ ?% I" s# q    end
* B6 Z: H  q& @; v! hend
% l4 A5 h$ _8 \6 t! N. A! O& a' D- Jy = 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.