logo
tsvpis

3.3.2. Алгоритм Дейкстры

Описание алгоритма Дейкстры

Ищем расстояние от нулевой вершины

S = {0}

D[i] = C(0,i) i = 0 … n

While S ≠ V do

  1. выбираем вершину w, которая принадлежит множеству вершин V\S (V без S) с минимальной стоимостью D(w);

  2. S := S + w (добавляем вершину w к множеству S);

  3. для всех вершинdo D(v):=min( D(v), D(w) + C(w,v) ) пересчитываем стоимости всех остальных вершин.

Пример. Рассмотрим работу алгоритма на уже знакомом графе:

Рисунок 3.7 – Исходный граф

Решение. Составим таблицу:

S

w

D(w)

D(1)

D(2)

D(3)

D(4)

0

Не определенны

25

15

7

2

(0,4)

4

2

25*

15

5

−**

(0,4,3)

3

5

25

9***

−

−

(0,4,3,2)

2

9

15

−

−

−

(0,4,3,2,1)

1

15

−

−

−

−

Пояснения.

* - 25 = min(25, 2 + ), где С(4,1) =  - стоимость переходы напрямую от 4 вершины к первой, так как эти вершины не соединены ребром;

** - стоимость маршрута от нулевой до четвертой вершины не пересчитывается, так как четвертая вершина уже вошла во множество S.

Прочерки в остальных ячейках таблицы также означают отсутствие пересчета маршрутов для соответствующих вершин;

*** - 9 = min(11, 5 + 4), где 4 – вес пути из 3 вершины во вторую.

Комментарии. В алгоритме Дейкстры на каждом шаге

S – растущее множество вершин, для которых уже найдены их подлинные стоимости;

w – добавляемая к множеству S вершина;

D[j] – минимально возможная стоимость маршрута следующего вида:

Рисунок 3.8.

Замечание. Алгоритм Дейкстры работает корректно, так как на каждом шаге стоимость каждой вершины пересчитывается по формуле (3.2), что соответствует выбор из двух маршрутов – старого и нового.

Оценим трудоемкость данного алгоритма.

В процессе реализации алгоритма Дейкстры n раз выполняется цикл While. Внутри цикла While имеется цикл For, в котором нам приходится пересчитывать n-1, n-2, n-3, …, 1 значений. Каждое из них – минимум из двух числе, одно из которых – сумма двух слагаемых.

Следовательно, получаем квадратичную трудоемкость:

T(n) = ((n-1) + (n-2) + … + 1)·2 ≈n2

То есть алгоритм Дейкстры в целом работает на порядок быстрее, чем алгоритм Форда-Беллмана.

Замечание. Алгоритм Дейкстры может работать только с графами, для которых стоимости переезда C(i,j) ≥ 0. Алгоритм Форда-Беллмана справляется с графами и с отрицательными стоимостями переезда, но работает дольше.