标号法求解单源点最短路径：
      var
      a:array[1..maxn,1..maxn] of integer;
      b:array[1..maxn] of integer; {b[i]指顶点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[i] then {对每一个已计算出最短路径的点}
      for j:=1 to n do
      if (not mark[j]) and (a[i,j]〉0) then 
      if (best=0) or (b[i]+a[i,j]〈best) then begin
      best:=b[i]+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}  

发表评论