6.12. Улучшения алгоритма Дейкстры

В матрице смежности из примера 5.11 отсутствие ребра показано О, тогда как в исходном алгоритме [7] используют знак  , что логично. Матрицу мы заменим другим описанием, ибо ее применение делает неизбежной оценку сложности О (n² ).

Граф G2 (см. п.5.11) описывают следующие пары (1-й элемент - номер узла, 2-й – вес ребра):

(2,20),(6,30),(4,30),(5,70),

(1,20),(4,20),(5,100),

(4,70),(5,40)₎(6,20),

(1,30),(2,20),(3₁70),

(1,70),(2,100),(3,40),(6,30),

(1,30),(3,20),(5,30) .

и оглавление этого списка, показывающее, что 4 первые пары отно­сятся к связям 1-го узла, 3 следующих - к связям 2-го узла и т.д. Другими словами, для построения оглавления надо задать степени stp узлов графа G2: 4, 3,3, 3, 4, 3.

Анализ программы примера 5.11 показывает, что нахождение миниму­ма путем перебора ведет к сложности О(n²) независимо от представле­ния графа. С целью сокращения затрат времени применим для выбора минимума структуру, а именно - динамическое сортдерево (п.1.8), образуемое непостоянными оценками d узлов. Минимальная из них будет в корне сортдерева, где ее просто найти и откуда ее легко исключить при переводе в ранг постоянной.

Улучшение оценки узла требует исключения прежней оценки и вне­дрение в сортдерево новой. Для нас - это единый акт продвижения измененной оценки "вниз", к корню, так как оценка может лишь уменьшиться. Оценку нового узла мы добавляем как лист сортдерева, ее место также уточняется движением "вниз".

Указанные операции требуют п р я м о г о обращения к d_j по номеру узла i. Применим оглавление og м а с с и в а d (сортдере­во представлено массивом), а в сортдереве вместе с оценками d_j при­дется хранить и номера j - мы разместим их в отдельном массиве nоm, "параллельном" массиву d.

Пример 6.12.

Изучим содержание массивов при поиске в графе G2, когда узел 6 уже использован как база, а из сортдерева его оценка (30₆) еще не исключена:

Теперь оценка 30₆ удаляется блоком Out; сначала ее место займет лист 60₁, но не удержится в корне дерева, будучи вытеснен "сыном" 40₃. В корне - очередной минимум:

Рассмотрелный процесс D-поиска с построением каркаса, имеющего заданный корень - узел L, осуществляет блок DeikOer. Подблок Vniz реализует продвижение оценок в сортдереве по мере их улучше­ния, подблок Out - удаление из корня оценки, ставшей постоянной.

Const n=6; m=10; т1=2*m;

Type spis = Array[1..m 1, 1..2] of word;

mas = Array[1..n] of word; vec = Array[1..n+1] of word;

Constopi:spis=((2,20),(6,30),(4,30),(5,70),( 1,20),(4,20),(5,100),

(4,70),(5,40),(6,20),(1,30),(2,20),(3,70),(1,70),

(2,100),(3,40),(6,30),(1,30),(3,20),(5,30));

stp: vec = (4,3,3,3,4,3,0); {Степени узлов графа G2 и ноль - в конце}

Var og,d,r:mas; j.Lword;

Procedure DeikDer(var opi:spis; stp:vec; var d,og,r:mas; L:word);

Var nom:mas; basa,g,dl,i,j,k,s,v,x:word;

Procedure Vniz(i:word); {Блокищетместодляновойоценки g узлаграфа}

Begin

Repeatj:= iShr 1; {Сдвигомвправокодапозицииiузласортдерева}

Ifg<d[j] Then { найдем позицию] его предшественника в дереве}

Begin d[i]:=d[j]; nom[i]:=nom[j]; og[nom[j]]:=i; i:=j End

Else j:=1

Until j=1;

d[i]:= g; nom[i]:= v; og[v]:= i; r[v]:= L {Достраиваемкаркас}

End {блока включения новой оценки или оценки нового узла в дерево};

ProcedureOut; Label 1; {В Турбо Паскале 7.0 вместо Goto 1 можно }

Beginj:=1; k:=2; { использовать оператор Break, исключив метку 1}

While k<i do

Begin If d[k+1] < d[k] Then k:= k+1;

If d[i] <= d[k] Then Goto 1;

d[j]:= d[k]; nom[j]:= nom[k]; og[nom[k]]:=j; j:=k; k:= k+k

End; 1: d[j]:= d[i]; nom[j]:= nom[i]; og[nom[i]]:=j

End {блока исключения корневого узла сортдерева};

Begin {Начало операторной части блока D-поиск,}

s:=0; For j:= 1 to n do s:= s + stp[j];

Ifs<>m1 ThenWriteln('Ошибка в описании или в значении m');

If s <> ml Then Exit;

stp[n+1 ]:= s+1; {Создаем оглавление stp описания граф:}

For j:= n downto 1 do stp[j]:= stp[j+1] - stp[j];

Fork:= 1 tondoog[kj:= 0; {"О" обозначает узел k вне окружени}

s:=n; i:=1; nom[1]:= L; d[1]:= 0; r[L]:=n+1;

Repeat L:= nom[1]; basa:= d[1]; {Используемтекущуюбазу – узел}

For k:= stp[L] to stp[L+1]-1 do

Beginv:= opi[k,1]; {v - номер смежного узла, ах – позиция}

x:=og[v]; { его оценки в массиве d, либо это 0}

If х<= i Then Begin g:= basa + opi[k,2];

If x = 0 Then Begin i:=i+1; Vniz(i) End

Else If g < d[x] Then Vniz(x)

End

End;

{Исключаем узел L из дерева, перенося его оценку в конец d:}

Out; i:=i-1; d[s]:= basa; nom[s]:= L; og[L]:=s; s:=s-1

Untili = 0 {Сортдерево пусто, следовательно, D-поиск завершен}

End{блока DeikDer, выполняющего D-поиск от заданного узла L};

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

DeikDer(opi, stp, d, og, r, L);

Writeln ('Длины кратчайших цепей, ведущих от узла L к узлам');

Writeln ('1 2 3 4 5 6 :');

For j:=1 to n do write(d[og[j]],' '); Readln

END.

Для вывода узлов кратчайшей цепи <Lj> применяйте блок OutPt из ответа к заданию 5.10. Заметим, что в результирующем массиве d оценки узлов расположены по убыванию их значений^*, а это дает; простой способ нахождения множества узлов, удаленных от узла L не более (не менее) чем на заданную величину Z.

Оценим данную модификацию алгоритма. Если число ребер m>>n, достаточно оценить сложность обработки ребер: рассматривается каждое ребро, при этом, кроме действий фиксированной сложности, которыми пренебрегаем, происходят операции в сортдереве. Их число - в расчете на одно ребро - зависит от высоты сортдерева, не превосходящей logn. Если исходить из максимума этого числа, получим асимптотическую ВС, равную О(m*logn). Если m и n одного порядка, оценка приобретает вид О(n + m*logn), ибо главный цикл Repeat работает с каждым узлом связного графа как с базой.

Если число m ребер графа приближается к максимуму О(n²), применять модифицированный алгоритм нет смысла, хотя особого проигрыша по времени и не будет - в сравнении с алгоритмом п.5.11.

Задание 6.12.

• Используя блок DeikDer (пример 5.12), найдите все узлы, расстоя­ние от которых до заданного узла X имеет значение в диапазоне от А до В. Сложность их выявления должна быть минимальной.