Алгоритм Дейкстры, реализованный на основе d-кучи
Представим d-кучу массивом имен name[1..n] и массивом ключей key[1..n] так, что key[i] является текущей оценкой длины кратчайшего пути от вершины s к вершине name[i]. В данном алгоритме (см. [4]), представленном процедурой LDG_DIJKSTRA_D-HEAP, также используется массив index[1..n], который должен поддерживаться так, чтобы index[name[i]]:= i при i=1, …, n. Для достижения этой цели каждая строка “{+}” в псевдокоде операций ВСПЛЫТИЕ и ПОГРУЖЕНИЕ должна быть заменена строкой “index[name[i]]:= i;”
procedure LDG_DIJKSTRA_D-HEAP (var dist; var up; ADJ; n,d,s);
begin
for i:= 1 to n do begin
up[i]:= 0; dist[i]:= +¥; index[i]:= i; name[i]:= i; key[i]:= +¥;
end;
key[s]:= 0; nq:= n; ОБРАЗОВАTЬ_ОЧЕРЕДЬ(name,key,nq,d);
while nq>0 do begin
ИЗЪЯТИЕ_МИНИМУМА(name1,key1,name,key,nq,d);
i:= name1; dist[i]:= key1;
p:= ADJ[i].next;
while p ≠ nil do begin j:= p^.name; jq:= index[j];
{*} if dist[jq] = +¥ then
if key[jq] > dist[i]+p^.w then begin
key[jq]:= dist[i]+p^.w;
ВСПЛЫТИЕ( jq,name,key,nq,d); up[j]:= i;
end;
p:= p^.next;
end;
end;
end;
Временная сложность алгоритма Дейкстры, реализованного на основе d-кучи, где d³2, оценивается сверху величиной O((n+m)×log n), так как алгоритм производит n ИЗЪЯТИЙ_МИНИМУМА и не более m ВСПЛЫТИЙ, каждое из которых осуществляется за время O(log n). Заметим также, что строку {*} можно убрать без какого бы то ни было влияния на правильность работы алгоритма.
Алгоритм Дейкстры, использующий метки
В рассматриваемой реализации данного алгоритма (см. [2]), представленной процедурой LDG_DIJKSTRA_MARK, массив h[1..n] является массивом меток: метка h[i]=0, если построение кратчайшего пути из вершины sв вершинуiне завершено, и h[i]=1 в противном случае.
procedure LDG_DIJKSTRA_MARK (var dist; var up; ADJ; s);
begin
for i:= 1 to n do begin up[i]:= 0; dist[i]:= +¥; h[i]:= 0 end;
dist[s]:= 0; nq:= n;
while nq>0 do begin
c:= 1; while h[c] ≠ 0 do c:= c+1;
i:= c; for k:= c+1 to n do if h[k]= 0 then if dist[i]>dist[k] then i:= k;
h[i]:= 1; nq:= nq-1; p:= ADJ[i].next;
while p ≠ nil do begin
j:= p^.name;
{*} if h[j] = 0 then
if dist[j] > dist[i]+p^.w then begin
dist[j] = dist[i]+p^.w; up[j]:= i;
end;
p:= p^.next;
end;
end;
end;
Временная сложность алгоритма Дейкстры, использующего метки, есть O(n2). Заметим, что также, как и раньше, строку {*} можно убрать без какого бы то ни было влияния на правильность работы алгоритма.
Алгоритм Форда–Беллмана
Алгоритм Форда–Беллмана (см. [5]), представленный процедурой LDG_FORD_BELLMAN, сначала полагает dist[s]=0 и dist[i]:= +¥ при всех iÎV\{s}, а затем (n-1) раз выполняет следующие действия:
для каждого ребра (i, j) Î E графа G = (V, E) такого, что j ≠ s, заменяет dist[j] на min{dist[j], dist[i]+W(i, j)}.
procedure LDG_FORD_BELLMAN (var dist; var up; ADJ; n,s);
begin
for i:= 1 to n do begin up[i]:= 0; dist[i]:= +¥ end; dist[s]:= 0;
for k:= 1 to n-1 do for i:= 1 to n do begin
p:= ADJ[i].next;
while p ≠ nil do begin
j:= p^.name;
if j ≠ s then if dist[j] > dist[i]+p^.w then begin
dist[j] := dist[i]+p^.w; up[j]:= i;
end;
p:= p^.next;
end;
end;
end;
Временная сложность алгоритма Форда-Беллмана есть O(n×m).
Задания для лабораторной работы № 1
Предлагается попарное сравнение различных алгоритмов нахождения кратчайших путей от вершины sÎV до всех остальных вершин в графе G = (V, E), имеющем n вершин и m ребер.
Варианты выбора пары алгоритмов A и B для сравнения:
Вариант d=1, …, 10
А - алгоритм Дейкстры, реализованный на основе (d+1)–кучи,
В - алгоритм Дейкстры, реализованный на основе (d+2)–кучи;
Вариант d=11, …, 20
А - алгоритм Дейкстры, реализованный на основе (d-9)–кучи,
В - алгоритм Дейкстры, использующий метки;
Вариант d=21, …, 30
А - алгоритм Дейкстры, реализованный на основе (d-19)–кучи,
В - алгоритм Форда-Беллмана;
Вариант 31
А - алгоритм Дейкстры, использующий метки,
В - алгоритм Форда-Беллмана.
Задание.
1. Написать программу, реализующую алгоритм А и алгоритм В.
2. Написать программу, реализующую алгоритм А и алгоритм В, для проведения экспериментов, в которых можно выбирать:
· число n вершин и число m ребер графа,
· натуральные числа q и r, являющиеся соответственно нижней и верхней границей для весов ребер графа.
Выходом данной программы должно быть время работы ТА алгоритма А и время работы ТВ алгоритма В в секундах.
3. Провести эксперименты на основе следующих данных:
3.1. n = 1, … ,104+1 с шагом 100, q = 1, r =106, количество ребер: а) m ≈ n2/10, б) m ≈ n2 (нарисовать графики функций TА(n) и ТВ(n) для обоих случаев);
3.2. n = 101, … ,104+1 с шагом 100, q = 1, r = 106, количество ребер: а) m ≈ 100×n, б) m ≈ 1000×n (нарисовать графики функций TА(n) и ТВ(n) для обоих случаев);
3.3. n = 104+1, m = 0, … ,107 с шагом 105, q = 1, r = 106 (нарисовать графики функций TА(m) и ТВ(m) );
3.4. n = 104+1, q = 1, r = 1, … ,200 с шагом 1, количество ребер: а) m ≈ n2, б) m ≈ 1000×n (нарисовать графики функций TА(r) и ТВ(r) для обоих случаев).
4. Сформулировать и обосновать вывод о том, в каких случаях целесообразно применять алгоритм А, а в каких - алгоритм В.