Алгоритм Дейкстры, реализованный на основе 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. Сформулировать и обосновать вывод о том, в каких случаях целесообразно применять алгоритм А, а в каких - алгоритм В.



Наши рекомендации