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

Пусть дан ориентированный граф 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

№ итераций	Numln	Num	St	Nm
начальная	[2, 2, 2, 1, 0, 1]	[0, 0, 0, 0, 0, 0]	[5]
	12.2.1.0, 0, 1]	[0, 0, 0, 0.1, 0]	[4]
	[1.2, 0, 0.0, 1]	[0, 0, 0, 2, 1, 0]	[3]
	[0.2, 0, 0, 0, 0]	[0, 0, 3.2.1, 0]	[6, 1]
	[0, 1, 0, 0, 0, 0]	[0.0, 3, 2.1, 4]	[1]
	[0, 0, 0, 0, 0, 01	[5, 0, 3, 2, 1, 4]	[2]
	[0, 0, 0, 0, 0, 0]	[5, 6, 3, 2, 1.4]	[]

 

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. Требуется «стыковка» новых номеров и матрицы А.