迪杰斯特拉(Dijkstra)算法

haige

带权图的最短路径问题的matlab函数代码
function y = shortest_path(i,j)
& _' U( @1 ?* Q* Da=load('A.mat');
A=a.a;
2 Y2 R& x* b, f# c: ^N = length(A);                                   t
9 @9 B* O! }; s' S, |! q: Y9 vS = zeros(1,N);                                 
# L( j" a! G5 r* X7 z  ZS(1) = i;                                       
dist = A(i,;                                   
! x0 O3 t  L2 ]# g' Y1 X# _flag = 0;                                       
count = 1;                                       
while (flag~=1)
* Z& d% L! A! z/ S& j    [value,position] = min(dist);               
: L, ]8 P) v1 |" i# s0 r$ ~" {    dist(i) = inf;                              
    if (position == j)
% i# c: e1 C8 _' l        flag = 1;
6 q% W  S5 e, V  U5 _; |% f    else
        count = count + 1;
        S(count) = position;
        for o = 1:N
$ F; L! N$ Y' a  _, s5 t" a            dist(o) = min(dist(o),dist(position)+A(position,o));
        end
        dist(position) = inf;                    % point can't back to itself,so weight = inf
: H# x/ x3 v  D9 Z  G- o+ W/ ?    end
end
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.