迪杰斯特拉(Dijkstra)算法

haige

带权图的最短路径问题的matlab函数代码
function y = shortest_path(i,j)
( g/ Y4 v- E- A  K. c, M1 Za=load('A.mat');
; u  c3 u( U) M7 L+ [! ^A=a.a;
N = length(A);                                   t
S = zeros(1,N);                                 
S(1) = i;                                       
dist = A(i,;                                   
flag = 0;                                       
count = 1;                                       
while (flag~=1)
    [value,position] = min(dist);               
    dist(i) = inf;                              
' {) g7 I4 p% \    if (position == j)
$ @- E" Z4 Y1 Y1 A5 m        flag = 1;
    else
        count = count + 1;
        S(count) = position;
        for o = 1:N
: c: e) k$ _3 P5 Z. Q            dist(o) = min(dist(o),dist(position)+A(position,o));
1 ^0 a; m: C5 q0 a1 k0 q        end
        dist(position) = inf;                    % point can't back to itself,so weight = inf
    end
" h7 }' @, t  n* qend
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.