dijkstra 算法.txt

Dijkstra 算法

var
     a:array[1..maxn,1..maxn] of integer;
     b,pre:array[1..maxn] of integer; {pre[i]指最短路径上I的前驱结点}
     mark:array[1..maxn] of boolean;
procedure dijkstra(v0:integer);
 begin
   fillchar(mark,sizeof(mark),false);
   for i:=1 to n do begin
     d[i]:=a[v0,i];
     if d[i]<>0 then pre[i]:=v0 else pre[i]:=0;
   end;
   mark[v0]:=true;
   repeat   {每循环一次加入一个离1集合最近的结点并调整其他结点的参数}
     min:=maxint; u:=0; {u记录离1集合最近的结点}
     for i:=1 to n do
       if (not mark[i]) and (d[i]<min) then begin
         u:=i; min:=d[i];
     end;
     if u<>0 then begin
       mark[u]:=true; 
       for i:=1 to n do
        if (not mark[i]) and (a[u,i]+d[u]<d[i]) then begin
          d[i]:=a[u,i]+d[u];
          pre[i]:=u;
       end;
     end;
   until u=0;
 end;