迪杰斯特拉(Dijkstra)算法

haige

带权图的最短路径问题的matlab函数代码
function y = shortest_path(i,j)
! S4 U+ T3 S( p8 }# `a=load('A.mat');
, |" t  a3 a. m5 s# qA=a.a;
N = length(A);                                   t
( U4 K- g) d- W) ^1 zS = zeros(1,N);                                 
" s2 g6 x8 w* |S(1) = i;                                       
4 m" a7 p4 R  v5 [4 [/ H  o0 |. ~0 Bdist = A(i,;                                   
& j, G/ `0 E2 E# ~9 u) Jflag = 0;                                       
count = 1;                                       
while (flag~=1)
7 g9 @% L) |! W9 g4 s7 K    [value,position] = min(dist);               
9 ]; W( ]/ A1 U% v& `/ Q    dist(i) = inf;                              
    if (position == j)
        flag = 1;
    else
6 {  v: Q' L, I3 N        count = count + 1;
        S(count) = position;
        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
. C8 ?% V0 B! v6 Y2 E    end
5 {( s3 |. G' O* J  @4 Xend
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.