6.10. Кратчайшие пути, ведущие от заданного узла X ко всем прочим

Имея широтный каркас с корнем X, находим все узлы кратчайшей цепи XY в

о б р а т н о й последовательности: Y, "отец" Y,..., X. Если их загрузить в стек и затем выгрузить, получим прямую после­довательность. Зная длину цепи, можно поступить проще, сразу раз­местив узлы в соответствующих позициях массива (узел X - в 1-й позиции). Длина цепи XY определяется ярусом каркаса, на кото­ром находится Y. Узел X занимает 0-й ярус, его "дети" - 1-й и т.д.

Заметим, что асимптотическая сложность нахождения одной цепи XY и множества таких цепей - для заданного X и разных Y - одна и та же: каркас мы строим в любом случае. Для нахождения одной цепи можно поиск в ширину начать от Y, чтобы сразу получить нужную последовательность ее узлов, но этот вариант для орграфов непригоден.

Пример 6.10.

Блок КаrX строит широтный каркас, начиная от X, и находит номер NN яруса, на котором лежит заданный узел Y. В основной програм­ме находим кратчайшую цепь

XY в графе Gl, записывая ее в массив В. Данный вариант поиска пригоден и для орграфов.

Constn=9; {Значение n не должно превышать 254}

Type matr=Array[1..n,1..n] of byte; vek=Array[1..n] of byte;

Const A: matr = ( (0,1,0,1,0,0,0,1,0),

(1,0,1,0,0,1,0,0,0),

(0,1,0,1,1,0,1,0,0),

(1,0,1,0,0,0,1,0,0),

(0,0,1,0,0,0,0,1,1),

(0,1,0,0,0,0,0,0,0), (0,0,1,1,0,0,0,0,0), (1,0,0,0,1,0,0,0,0), (0,0,0,0.1,0,0,0,0));

Var R,b:vek; j,k,NN,X,Y:byte;

Procedure KarX (Var A:matr; X,Y:byte; Var R:vek; Var NN:byte);

Var O:vek; i,ii,j,k,L:byte;

Begin For j:=1 to n do R[j]:=0;

i:=1; k:=1; 0[kj:=X; R[X]:=n+1; NN:=0; {NN - номеряруса}

Repeatii:=k; NN:= NN+1; {Подготовка формирования поколения}

Repeat {Начало цикла заполнения NN-ro яруса}

L:= O[i]; {Номер L текущего узла берем из очереди}

For j:=1 to n do If (A[L,j] <> 0) And (R[j] = 0) Then Begin R[j]:=L; k:=k+1; O[k]:=j; If j=YThen Exit End; i:=i+1 {/ - позицияочередного "отца", если i <= k}

Untili>ii {Конец заполнения яруса (формирования поколения)}

Untili>k {Завершение поиска в ширину при ненахождении цепи}

End;

BEGIN X:=5; Y:=6; KarX (A, X, Y, R, NN); k:= Y;

If R[Y] = 0 Then Writeln ('Цепь ', X, ' -> ', Y, ' ненайдена')

Else

Begin Writeln('Длинакратчайшейцепи ',X, '->',Y, ' равна ',NN);

For j:=NN+1 downto 1 do Begin b[j]:= k; k:= R[k] End;

Write ('Кратчайшаяцепь: ', b[1]); For j:=2 to NN+1 do Write(', ', b[j])

End; Readln;

END.

Переменная ii в блоке KarX фиксирует границу поколения в очере­ди О; при завершении его обработки граница ii смещается. Работа блока прекращается при достижении конечного узла Y.

Задание 6.10.

• Составьте программу нахождения множества кратчайших цепей, начинающихся в узле X, с блоком формирования широтного каркаса графа и блоком вывода одной цепи, выбранной из множества цепей.

6.11. Алгоритм Дейкстры нахождения кратчайших путей во взвешенном графе

Поскольку рассматриваемые ниже методы применимы и к орграфам, термины "путь", "дуга" далее используются как синонимы терминов "цепь", "ребро" соответственно.

Метод Дейкстры применяют для нахождения кратчайших путей XY во взвешенном связном графе при положительных весах ребер. Длину кратчайшего пути, определяемую как сумма весов ребер, назовем расстоянием между узлами X, Y. Пример применения - выявление кратчайших путей в системе дорог.

Искомые кратчайшие пути выявляются на второй фазе работы, а пер­вая фаза похожа на поиск в ширину: процесс начинается от "точки возмущения" - узла X, вовлекая затем “детей” X, "внуков" и т.д., т.е. своего рода "плотное" окружение X расширяется^*.

Каждый новый узел окружения получает оценку - длину пути к нему от узла X. Выявляемые кратчайшие пути используют как нача­ла кратчайших путей к следующим узлам: в неэлементарный крат­чайший путь входят кратчайшие пути до и от промежуточных узлов. Может быть несколько вариантов пути к узлу, поэтому оценки не­постоянны, улучшаются, и возможно не раз. Узлам вне окружения можно дать оценку  ; она рано или поздно будет заменена реальной.

Итак, для получения оценки даже одного узла Y, т.е. длины пути XY, приходится в общем случае заниматься оценками многих узлов окружения X, в которое со временем вовлекается Y. Назовем этот процесс D-поиском.

Рассмотрим пример D-поиска в неориентированном графе G2; номера узлов обведены кругами, а веса ребер даны возле ребер:

Граф G2

Начнем поиск кратчайшей из цепей 5  4, а этих цепей - более десятка. Даем оценку 0 исходному узлу X, т.е. узлу 5. Она постоян­на. Затем оценки "детей" X получаем, прибавляя к ней длину ребра.

Итак, получены оценки ближайшего окружения 70₁, 100₂, 40₃, 30₆ (индекс - номер узла). Наименьшая из них (30₆) - окончательна. В самом деле, цепь - ребро {5,6} кратчайшая, ибо оценка иных цепей <5  6> это сумма положительных членов, где первое слагаемое больше 30.

Узел 6 становится базой для выработки оценок смежных узлов. Непостоянная оценка 70₁, заменяется на 60₁: путь к узлу 1 через узел 6 короче прежнего - ребра {5,1}. Оценка 40₃ не заменяется (30₆ + 20 > 40₃). Именно она теперь оказывается минимальной среди непостоянных оценок и причисляется к постоянным по той же логике, какую применили к узлу 6. Узел 3 - новая база.

Итак, всякий раз выбираем минимальную непостоянную оценку узла, делаем ее постоянной, т.е. исключаем из числа непостоянных, а оценки смежных с ним узлов, если не получаем впервые, то улучшаем, когда это возможно. В отличие от поиска в ширину порядок прохождения базовых узлов не соответствует дисциплине FIFO, поэтому очередь (структура) здесь неуместна.

Узел 4 - конечный узел искомой цепи - впервые получает оценку (110₄ = 40₃ + 70), когда база - узел 3, а затем базой становится узел 1 и оценка улучшается. Оценка 90₄ окончательна, но удостоверяется этот факт, только когда она оказывается наименьшей среди непостоянных оценок.

В методе Дейкстры кратчайшие пути "прорисовываются" на 2-й фазе работы. Откажемся от фазы 2 и будем уже на 1-й фазе строить каркас графа (D-каркас), образуемый кратчайшими путями - как при поиске в ширину, с тем отличием, что ссылка r_ij на предшественника ("отца") узла может заменяться, и не раз: когда оценка узла улучшается, текущий базовый узел становится его новым "отцом". Иначе говоря, каркас не сразу приобретает окончательный вид, в котором любой цепной список ведет к узлу X через узлы кратчайшего пути. Описанием "однофазного" алгоритма является блок Deiks.

Пример 6.11.

Найдем длины d_j кратчайших цепей <Х j> для всех узлов j при; заданном узле X и построим D-каркас r графа G2 (см. выше). Текущий базовый узел обозначим L. Вначале это узел X.

Constn=6;

Type tip=word; matr=Array[1..n,1..n] of tip;

mas=Array[1..n] of longint;

Const A:matr=(( 0, 20, 0,30,70, 30),

(20, 0,0, 20, 100,0),

( 0, 0, 0, 70, 40, 20),

(30, 20, 70, 0, 0, 0),

(70,100,40,0,0,30),

(30, 0, 20, 0, 30, 0));

Var d,r:mas; i,X:word;

Procedure Deiks(var A:matr; var d,r:mas; X:word; max:tip);

Var i,j,L:word; min,p:longint;

Begin {Вначале оценки d узлов - отрицательные числа большой}

{абсолютной величины; минус - признак непостоянной оценки} Forj:=1 tondoBegind[j]:=-max; r[j]=0 End; d[X]:=0;

r[X] :=n+1; L:=X; {Мнимая ссылка n+1 - признак корня X каркаса}

Repeat For j:=1 to n do If A[L,j]<>0 then

Beginp:= - (d[L]+A[L,j]); {Возможная новая оценка узла j}

If p > d[j] then Begin d[j]:= p; r[j]:=L End End;

min:= - max; {Ниже цикл поиска минимальной по модулю временной оценки}

For i:=1 to n do If(d[i]<0) And (d[i]>min) then

Begin min:=d[i]; L:=i End;

d[L]:=Abs(d[L]) {Превращение оценки в постоянную; L-новая база}

Untilmin= - max {Если непостоянных оценок не осталось, }

End; {каркас построен, а значение min равно -max}

BEGIN

Writeln('Укажите отправной узел: '); Readln(X);

Deiks(a,d,r,X, 1000); Writeln;

For i:=1 to n do Write(r[i],' '); Readln;

END.

Для Х=5 программа выводит следующее содержание массива r:

6 1 5 1 7 5

1 2 3 4 5 6

показывая, что узел 5 - корень каркаса, ибо ссылается на несущест­вующий узел 7, а на корень ссылаются узлы 3 и 6. Узлы 2 и 4 ссылаются на 1, а узел 1 - на 6. Итак, получен D-каркас, выделен­ный жирным в изображении графа G2.

Задание 6.11.

• Примените блок Deiks к орграфу, используя как отправной узел:

а) исток; б) сток; в) узел, не являющийся стоком и истоком.

Объясните результат. Для вывода искомых кратчайших путей используйте блок OutPt из ответа к заданию 5.10.