迪杰斯特拉(Dijkstra)算法

haige

带权图的最短路径问题的matlab函数代码
* S, {, z3 Q& Q3 Y. ^function y = shortest_path(i,j)
; W8 D" G) K8 o! g' Za=load('A.mat');
A=a.a;
; ?/ z2 ~4 |" [- M0 ~. J8 iN = length(A);                                   t
# n9 \+ B( R0 B- GS = zeros(1,N);                                 
S(1) = i;                                       
dist = A(i,;                                   
* V/ v  H# v+ M2 [5 Y2 oflag = 0;                                       
# ]" c" _, w  E/ \7 X3 r! p! ycount = 1;                                       
) p2 g3 m3 E3 n! n( H7 dwhile (flag~=1)
    [value,position] = min(dist);               
5 L/ }" w5 a3 {0 |8 w9 X* s" H    dist(i) = inf;                              
& \9 F5 Q: C; n3 c' V+ O, t' K    if (position == j)
! }- n% P9 r% f        flag = 1;
9 Z8 s! s( V# Y& u( D1 Z1 B  X    else
8 j; Z2 [( o, O% p9 e% d        count = count + 1;
        S(count) = position;
9 [  }0 c5 I+ h, }7 ]2 G. H        for o = 1:N
            dist(o) = min(dist(o),dist(position)+A(position,o));
        end
6 |5 L4 |: s- v, `        dist(position) = inf;                    % point can't back to itself,so weight = inf
    end
/ \! w& P4 S. B  |/ `. |' Pend
y = 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.