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; 〈d[i]) then begin d[i]:=a[u,i]+d[u]; pre[i]:=u; end; end; until u=0; end; 

发表评论