Программа поиска путей в графах и сетях

{ ПРОГРАММА ПОИСКА ПУТЕЙ В ГРАФАХ И СЕТЯХ }
{ Алгоритм Л.Р.Форда, Р.Е.Беллмана }
{ Разработано: Денегин С.Н. }
{ Дата: 15 мая 1995 }
Program Net; { поиск минимального пути в орграфе }
Uses Crt;
Const
NMAX = 50;
MAX = 1000000;
Var
C: Array [1..NMAX,1..NMAX] of Real; { стоимость передачи }
L: Array [1..NMAX,0..NMAX-1] of Real;
Path: Array [1..NMAX,1..NMAX] of Word;
I,J,K: Word;
N,M: Word;
Procedure ReadData(FileName: String);
{в первой строке стоит число узлов }
{строка состоит из:<узел A> <кол-во связей> (<узел B> <стоимость передачи>)... }
Var
F: Text;
A,B: Word;
Connect: Integer;
Begin
Assign(F,FileName);
Reset(F);
ReadLn(F);
ReadLn(F,N);
For I:=1 To N Do
For J:=1 To N Do
C[I,J]:=MAX;
Connect:= 0;
Repeat
Read(F,A,M);
For I:=1 to M Do Begin
Read(F,B,C[A,B]);
Connect := Connect + 1;
End;
Until EOF(F);
Close(F);
WriteLn('Результаты работы программы NET-PATH:');
WriteLn('Число станций в сети: ',N);
WriteLn('Число связей в сети: ',Connect);
WriteLn;
End { ReadData };
Procedure MakeL;
{ вычисление массива чисел Лямбда }
Begin
For I:=0 To N-1 Do L[1,I]:=0;
For I:=2 To N Do L[I,0]:=MAX;
For K:=1 To N-1 Do
For I:=2 To N Do Begin
L[I,K]:=MAX;
For J:=1 To N Do
If C[J,I]+L[J,K-1]<=L[I,K] Then Begin
L[I,K]:=C[J,I]+L[J,K-1];
Path[I,K]:=J;
End;
End;
End { MakeL };
Procedure GetLowCostPath(Point: Word);
Begin
K:=N-1;
Repeat
K:=K-1;
Until (L[Point,K-1]>L[Point,K]) Or (K=1);
WriteLn('Самый дешевый маршрут из 1 в ',Point,' узел состоит из ',K,' ходов и стоит ',L[Point,K]:1:0,' тыс.руб.');
For K:=K DownTo 0 Do Begin
Write(Point);
If K<>0 Then Write(' <- ');
Point:=Path[Point,K];
End;
WriteLn;
End { GetLowCostPath };
Procedure GetShotestPath(Point: Word);
Begin
K:=0;
Repeat
K:=K+1;
Until (L[Point,K]<MAX) Or (K=N-1);
If L[Point,K]=MAX Then WriteLn('Узел не может быть достигнут')
Else Begin
WriteLn('Самый короткий путь из 1 в ',Point,' узел состоит из ',K,' ходов и стоит ',L[Point,K]:1:0,' тыс.руб.');
For K:=K DownTo 0 Do Begin
Write(Point);
If K<>0 Then Write(' <- ');
Point:=Path[Point,K];
End;
End;
WriteLn;
End { GetShotestPath };
Begin
ClrScr;
ReadData('net-path.cfg');
MakeL;
GetLowCostPath(16);
GetShotestPath(16);
GetLowCostPath(19);
GetShotestPath(19);
GetLowCostPath(42);
GetShotestPath(42);
GetLowCostPath(30);
GetShotestPath(30);
End.