Пути в бесконтурном графе

Пусть дан ориентированный граф G=<V,E> без контуров, веса дуг произвольны. Результатом является — массив кратчайших расстояний (длин) D от фиксированной вершины s до всех остальных. Утверждение — в произвольном бесконтурном графе вершины можно перенумеровать так, что для каждой дуги (i, j) номер вершины i будет меньше номера вершины j.

Пример.Введем следующие структуры данных:

массив NumIn, NumIn[i] определяет число дуг, входящих в вершину с но­мером i;

массив Num. Num[i] определяет новый номер вершины i;

массив St, для хранения номеров вершин, в которые захо­дит нулевое количество дуг. Работа с массивом осуществ­ляется по принципу стека;

переменная nm, текущий номер вершины.

Идея алгоритма.

Вершина i, имеющая нулевое значение Nu­mIn (а такая вершина на начальном этапе обязательно есть в силу отсутствия контуров в графе), заносится в St, ей присваи­вается текущее значение nm (запоминается в Num), и изменя­ются значения элементов NumIn для всех вершин, связанных с i. Процесс продолжается до тех пор, пока St не пуст.

На рисунке 6 приведен пример графа, а в таблице 3 представлены результаты трассировки работы алгоритма для этого примера.

Рис. 6

Таблица 3

Procedure Change_Num; { *A, Num — глобальные струк туры данных. *}

Var NumIn,St:Array[1..N] Of Integer;

i,j,u,nm,yk:Integer;

Begin

FillChar (Numln,SizeOf (Numln) ,0) ;

For i:=2 To N Do

For j:-1 To N Do

If A[i,j]<>0 Then Inc (Numln (j}) ;

nm:=0;yk:=0;

For To N Do

If Numln [i]=0

Then

Begin Inc (yk);Stack[yk]:=i; End;

While yk<>0 Do

Begin

u:=Stack[yk];Dec[yk];Inc(nm);Num[u]:=nm;

For i:=1 To N Do

If A[u,i]<>0 Then

Begin

Dec(Numln[i));

If Numln [i] =0 Then

Begin Inc(yk); Stack (yk} ;=i; End;

End;

End;

End;

Итак, пусть для графа G выполнено условие утверждения (вершины перенумерованы) и нам необходимо найти кратчай­шие пути (их длины) от первой вершины до всех остальных. Пусть мы находим оценку для вершины с номером i. Достаточ­но просмотреть вершины, из которых идут дуги в вершину с номером i. Они имеют меньшие номера, и оценки для них уже известны. Остается выбрать меньшую из них.

Procedure Dist;(*D, А - глобальные величины.*}

Var i, j : Integer;

Begin

D[1]:=0;

For i:=2 To N Do D[i] : =МахInt-<максимальное значение в матрице смежности А>;{*Определите, с какой целью вычитается из Maxlnt максимальный элемент матрицы А. *}

For i:=2 То N Do

For j :=1 To i-1 Do

If A[j,i]<>

Then D[i] :=Min (D[i] ,D[j] +A[j, i]) ;

End;

Процедура написана в предположении о том, что i и j — но­вые номера вершин и A[i,j] соответствует этим номерам. Одна­ко это не так. Новые номера по результатам работы предыду­щей процедуры хранятся в массиве Num. Требуется «стыковка» новых номеров и матрицы А.