Advertisement
WadeRollins2710

Find Shortest Path Algorithm in Pascal

Oct 5th, 2016
108
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Pascal 2.56 KB | None | 0 0
  1. Program ShortestPath;
  2. Uses crt;
  3. Var
  4.         A: Array [1..10000,1..10000] of Integer;
  5.         Trace: Array [1..10000,1..10000] of Integer;
  6.         n, m, Start, Finish: Integer;
  7.         f: Text;
  8. Procedure Input;
  9.         Var
  10.                 i, PosStart, PosEnd, Length, j: Integer;
  11.         Begin
  12.                 Assign(f,'MAP.INP');
  13.                 Reset(f);
  14.                 Readln(f,n,m);
  15.                 Readln(f,Start,Finish);
  16.                 For i:=1 to n do
  17.                         For j:=1 to n do
  18.                                 If i=j then A[i,j]:=0 else A[i,j]:=1001;
  19.                 For i:=1 to m do
  20.                         Begin
  21.                                 Readln(f,PosStart,PosEnd,Length);
  22.                                 A[PosStart,PosEnd]:=Length;
  23.                                 A[PosEnd,PosStart]:=Length;
  24.                         End;
  25.                 Close(f);
  26.         End;
  27. Procedure Process;
  28.         Var
  29.                 i, j, k: Integer;
  30.         Begin
  31.                 For i:=1 to n do
  32.                         For j:=1 to n do
  33.                                 Trace[i,j]:=j;
  34.                 For k:=1 to n do
  35.                         For i:=1 to n do
  36.                                 For j:=1 to n do
  37.                                         If A[i,j]>A[i,k]+A[k,j] then
  38.                                                 Begin
  39.                                                         A[i,j]:=A[i,k]+A[k,j];
  40.                                                         Trace[i,j]:=k;
  41.                                                 End;
  42.                 For i:=1 to n do
  43.                         Begin
  44.                                 For j:=1 to n do
  45.                                         Write(Trace[i,j]:3);
  46.                                 Writeln;
  47.                         End;
  48.         End;
  49. Procedure Output;
  50.         Begin
  51.                 Assign(f,'MAP.OUT');
  52.                 Rewrite(f);
  53.                 If A[Start,Finish]=MaxInt then Writeln(f,'NONE')
  54.                 else
  55.                         Begin
  56.                                 Writeln(f,A[Start,Finish]);
  57.                                 Write(f,Start,'-');
  58.                                 While (Start<>Finish) do
  59.                                         Begin
  60.                                                 Write(f,Trace[Start,Finish],'-');
  61.                                                 Start:=Trace[Start,Finish];
  62.                                         End;
  63.                         End;
  64.                 Close(f);
  65.         End;
  66. Begin
  67.         Input;
  68.         Process;
  69.         Output;
  70. End.
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement