Случай неотрицательных весов — алгоритм Дейкстры

Известны более эффективные алгоритмы для двух важных случаев, а именно: когда веса всех дуг неотрицательны или когда граф бесконтурный.

Сначала 3.3. Случай неотрицательных весов — алгоритм Дейкетры 2 (3)

Рис. 3.1: Работа алгоритма Форда-Беллмана

Опишем алгоритм для первого случая - алгоритм Дейкстры [11]. Вторым случаем займемся в следующем параграфе.
Алгоритм 3.3. (Нахождение расстояния от источника до всех остальных вершин в графе с неотрицательными весами дуг — метод Дейкстры.)

Данные: Ориентированный граф <V,E> с выделенным источником s є V, матрица весов дуг A [u, v], u,v є V (все веса неотрицательны).

Результаты: Расстояния от источника до всех вершин графа D[u] г = d(s,v), v є V.

1. begin
2. for v є V do D[v]:= А[s,u];
3. D[s]:= 0; T:= V\{s};
4. while T? 0 do
5. begin
6. u:= произвольная вершина r є Т, такая, что
D[r] = min{D[p]: p є T};
7. Т:=Т\{u};
8. for v є T do D[v]:= min(D[v], D[u] + A[u,v])
9. end
10. end

Чтобы понять действие алгоритма, покажем, что следующее условие является инвариантом цикла 4:
для любого v є V\T D[v] =d(s,u),
для любого v є T, D[v]= длине кратчайшего из тех путей из s в v,
для которых предпоследняя вершина принадлежит множеству V\Т.

//

В самом деле, в строке 5 мы находим вершину u є Т, такую что значение D[u] является минимальным (из всех) значением D[t]t для t є Т. Покажем, что D[u] = d(s,u). Это именно так, потому что если кратчайший путь из s в u имеет длину меньше D[u], то в силу второй части условия (3.6) его предпоследняя вершина принадлежит множеству Т. Пусть t будет первой вершиной пути, принадлежащей множеству Т (см. рис. 3.2). Начальный отрезок нашего пути из в в t составляет кратчайший путь из s в t, причем его предпоследняя вершина не принадлежит множеству Т. По второй части условия (3.6) имеем D[t]=d(s, t). Используя предположение о неотрицательности весов, получаем

D[t]=d(s,t)?d(s,u)<D[u]

вопреки принципу, по которому была выбрана вершина u.

Таким образом, D[u] = d(s, u) и мы можем в строке 7 удалить и из множества T, не нарушая первой части условия (3.3). Чтобы обеспечить выполнение также и второй части этого условия, следует еще проверить пути из s в v є Т, предпоследняя вершина в которых есть и, и выполнить актуализацию переменных D[v], v є V. Именно это выполняет цикл 8.

Очевидно, что условие (3.6) выполняется при входе в цикл 4. По окончании действия алгоритма Т = 0, а следовательно, согласно условию (3.6), D[u] = d(s,v), v є V. Перейдем теперь к оценке сложности алгоритма Дейкстры. Цикл 4 выполняется п — 1 раз, причем каждое его выполнение требует O(n) шагов: O(n) шагов для нахождения вершины м в строке 6 (предполагаем, что множество Т представлено списком) и O(n) шагов для выполнения цикла 8. Таким образом, сложность алгоритма есть

Тщательно подбирая структуры данных, можно получить вариант алгоритма со сложностью O(m log n). Для этого множество Т нужно представить бинарным деревом с высотой O(log n) и с таким свойством, что для произвольных его вершин u и v
если u - сын и, то D[u]? D[v] (3.7)
(подобная структура данных используется в алгоритме сортировки Heapsort, см. [21], [1]). Вершина и, для которой значение D[u] минимально, является тогда корнем дерева. Этот корень можно устранить за O(log n) шагов, сохраняя свойство уменьшения значения D[u] на каждом пути до корня. Достаточно сместить на место корня его сына я с большим (или равным) значением D[ j ], затем на освободившееся место передвинуть сына вершины s с большим значением D[ j ] и т.д. Если граф представлен списками ЗАПИСЬ[u], u є V. то строку 8 можно заменить на:

for v є ЗАПИСЬ [u] do if D[u] + A[v,u] < D[v] then begin D[v];= D[u] + A[u,v]; передвинуть вершину в дереве в направлении корня так, чтобы сохранить условие (3.7) end

Если предположить существование таблицы указателей на вершины нашего дерева, то передвижение вершины v, о которой идет речь в данной части раздела, может быть осуществлено за O(log n) шагов. Достаточно заменять v поочередно вершинами, находящимися непосредственно над ней.

В алгоритме, модифицированном таким способом, каждая дуга графа анализируется в точности один раз. причем с этим связано О (log n) шагов на передвижение соответствующей вершины в дереве, представляющем множество Т. Это дает в сумме O(m log n) шагов. Сюда нужно добавить O(n log n) шагов, необходимых для построения нашего дерева и для устранения n-1 раз из него корня. Общая сложность алгоритма есть O(m log n) (см. задачу 3.6).

Неизвестно, существует ли алгоритм сложности 0(m) нахождения расстояния от фиксированной вершины до всех остальных вершин графа с неотрицательными весами всех дуг. Можно показать, что существует константа С, такая что эта задача для произвольного к > 0 может быть решена за время

Работа алгоритма Дейкстры проиллюстрирована на рис. 3.3 {V = {1,...,6}, веса дуг даны в скобках, значения D[v], v є Т. обозначены кружками, минимальные значения — двойными кружками).

Дата добавления: 2014-01-07