shortest.pas

来自「迪杰斯特拉最短路径算法」· PAS 代码 · 共 57 行

  program p148;
 const
 Ifn='input.txt';
 Ofn='output.txt';
 maxN=100;
  var
   map:array[1..maxN,1..maxN] of integer;
   dist:array[1..maxN] of integer;
   Mark:array[1..maxN] of boolean;
   N,K:integer;
   fp:text;
  procedure init;
   var i,j:integer;
   begin
     Assign(fp,ifn);reset(fp);
     readln(fp,N,k);
     for i:=1 to n do
       for j:=1 to n do read(fp,map[i,j]);
     close(fp);
   end;
  procedure Main;
  var
    i,j,min,minj,temp:integer;
  begin
    fillchar(mark,sizeof(mark),0);
    for i:=1 to n do dist[i]:=maxint;
    dist[k]:=0;
    for j:=1 to n do begin
     min:=maxint;
     for j:=1 to n do
        if not mark[j] and (dist[j]<min) then begin
            min:=dist[j];
            minj:=j;
        end;
      mark[minj]:=true;
      for j:=1 to n do
       if not mark[j] and (map[minj,j]>0) then begin
          temp:=dist[minj]+map[minj,j];
          if temp<dist[j] then dist[j]:=temp;
       end;
      end;
   end;
  procedure show;
  var i:integer;
  begin
     assign(fp,ofn);  rewrite(fp);
     for i:=1 to n do write(fp,dist[i],' ');
     close(fp);
  end;
  BEGIN
  init;
  main;
  show;
  end.