Программа кратчайшего пути на орграфе Program Short; {Кратчайшие пути на графе

155


154

Глава 6. Введение в теорию графов. Алгоритмы на графах
6.9. Кратчайшие пути на графе

Алгоритм 6.12. Программа кратчайшего пути на орграфе
Program Short; {Кратчайшие пути на графе)
uses CRT,DOS;

Const

nVertex=50; {Максимальное количество вершин}

Type
TypeMark=array[0..nVertex] of Boolean; TypeDist=array[0..nVertex] of Longlnt; TypePrev=array[0..nVertex] of Integer; TypeWeight=array[0..nVertex,0..nVertex] of Integer;

Var
f :Text; { Текстовый файл }

nX :Integer; { Количество вершин в графе }

Mark :TypeMark; (Признаки временных и постоянных меток}

Dist :TypeDist; { Значения текущих меток вершин

(расстояния)}

Prev rTypePrev; { Указатель на ближайшую вершину } We :TypeWeight; { Матрица весов ребер графа } хО :Integer; { Вершина начала пути } z :Integer; { Вершина конца пути } у :Integer; (Последняя вершина с постоянной меткой}

Var
i,j,x :Integer; weight :Longlnt; begin

Assign(f,'Short.in');

Reset(f);(Файл открыт для чтения}

{Ввод исходных данных]
Read(f,xO); (Начальная вершина пути}

Read(f,z); (Конечная вершина пути}

Read(f,nX); (Количество вершин в графе}

пХ:=пХ-1; (* Х={О,1,2,...,пХ} - множество вершин *)

for i:=0 to nX do begin

for j:=0 to nX do begin

Read(f,We[i,j]); ( Ввод матрицы весов }

if We[i,j]=0 then We [i, j ] :=$7f f f; {-f бесконечность }

end; end;

Close(f);

Assign
(ft ' Short.out'); Rewrite(f); (Файл открыт для записи}

for x:=0 to nX do begin
Mark[x]:=FALSE; Distfx]:=$7fffffff; end;

у:=хО;
{Последняя вершина с постоянной меткой} Mark[у]:=TRUE; Dist[у]:=0;

while not Mark[z] do begin
{
Обновить временные метки]
for x:=0 to nX do if not Mark[x] and

( Dist[x]>Dist[y]+We[y,x] ) then begin Dist[x]:=Dist[y]+We[y,x]; Prev[x]:=y; end;

(Поиск вершины с минимальной временной меткой] weight:=$7fffffff;

for x:=0 to nX do if not Mark[x] then if weight>Dist[x] then begin weight:=Dist[x]; y:=x; end;

Mark[y]:=TRUE; end;

Write(f,'Вершины пути='); x:=z;

while x<>xO do begin Write(f,x:2); x:=Prev[x]; end;

WriteLn(f,x:2);

WriteLn(f,'Длина пути= \Dist[z]); Close(f); end.

Рассмотрим пример расчета по программе алгоритма 6.12 по­иска кратчайшего пути на графе, показанном на рис. 6.21. Исход­ные данные графа представляются матрицей весов его ребер в текстовом файле Short.in со следующей структурой:
•
в первой строке определяется номер начальной вершины пути
х$\
•
во второй строке определяется номер конечной вершины пути z;
•
в третьей строке указывается количество
пХ вершин в графе;
•
в следующих «^строках определяются строки матрицы весов [w^] графа.
<</multicol>