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

Вид материала

Программа

Содержание Var i,j,x :Integer; weight :Longlnt; begin Assign(f,'Short.in'); Reset(f);(Файл открыт для чтения} {Ввод Обновить временные метки]

Подобный материал:

• Программа «Определение кратчайшего пути в графе» Программа «Определение кратчайшего, 222.18kb.
• Вопросы к теоретическому зачету группы с (sis ­­– 2003), 29.23kb.
• В настоящее время существует множество задач, для решения которых требуется построить, 25.86kb.
• Проблема выбора пути в поэзии Н. М. Рубцова как способ раскрытия внутренней позиции, 92.16kb.
• Программа VI научно-практической конференции «На пути к эффективному животноводству», 45.78kb.
• Специалисты по го и чс предлагают к ознакомлению правила поведения в условиях паводков, 22.04kb.
• Изнеможение и наказание русской земли, 112.44kb.
• Алгоритмы на графах. Обходы графов. Кратчайшие пути. Остовные деревья, 114.51kb.
• Проведение геодезических работ при изысканиях, строительстве и эксплуатации пути; выявление, 62.07kb.
• Методы контрацепции и пути достижения контрацептивного эффекта, 212.19kb.

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] графа.