最短路径

最短路径
A.标号法求解单源点最短路径：
  var
    a:array[1..maxn,1..maxn] of integer;
    b:array[1..maxn] of integer; {b指顶点i到源点的最短路径}
    mark:array[1..maxn] of boolean;
  procedure bhf;
    var
    best,best_j:integer;
    begin
    fillchar(mark,sizeof(mark),false);
  mark[1]:=true; b[1]:=0;{1为源点}
  repeat
    best:=0;
      for i:=1 to n do
      If mark then {对每一个已计算出最短路径的点}
      for j:=1 to n do
        if (not mark[j]) and (a[i,j]>0) then
        if (best=0) or (b+a[i,j]<best) then begin
        best:=b+a[i,j]; best_j:=j;
      end;
    if best>0 then begin
      b[best_j]:=best；mark[best_j]:=true;
    end;
    until best=0;
    end;{bhf}
  B.Floyed算法求解所有顶点对之间的最短路径：
    procedure floyed;
    begin
for I:=1 to n do
for j:=1 to n do
if a[I,j]>0 then p[I,j]:=I else p[I,j]:=0; {p[I,j]表示I到j的最短路径上j的前驱结点}
  for k:=1 to n do {枚举中间结点}
  for i:=1 to n do
    for j:=1 to n do
      if a[i,k]+a[j,k]<a[i,j] then begin
    a[i,j]:=a[i,k]+a[k,j];
        p[I,j]:=p[k,j];
    end;
    end;
C. Dijkstra 算法：
var
    a:array[1..maxn,1..maxn] of integer;
    b,pre:array[1..maxn] of integer; {pre指最短路径上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:=a[v0,i];
    if d<>0 then pre:=v0 else pre:=0;
  end;
  mark[v0]:=true;
  repeat   {每循环一次加入一个离1集合最近的结点并调整其他结点的参数}
    min:=maxint; u:=0; {u记录离1集合最近的结点}
    for i:=1 to n do
    if (not mark) and (d<min) then begin
      u:=i; min:=d;
    end;
    if u<>0 then begin
    mark:=true;
    for i:=1 to n do
      if (not mark) and (a[u,i]+d<d) then begin
      d:=a[u,i]+d;
      pre:=u;
    end;
    end;
  until u=0;
end;