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 ≈n²

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

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

3.4. Нахождение диаметра, радиуса и центра графа

Определения.

Диаметров графа (взвешенного) называется максимально возможное расстояние между вершинами.

- максимальная стоимость маршрута u → v.

Радиусом графа называется минимально возможный радиус круга (центра круга выбирается среди всех вершин), внутри которого помещается весь граф.

где - минимально возможный радиус круга (в который входит весь граф) с центром в вершинеu.

Центр графа - та вершина u₀, для которой достигается минимально возможный радиус круга: u₀: r(u₀) = r(G).

При применении алгоритма Дейкстры и диаметр, и радиус графа можно найти за T = n·n² операция, где n² – трудоемкость однократного применения алгоритма Дейкстры.

Алгоритм Дейкстры мы запускаем n раз: с начала от v₀, потом от v₁ и т.д. перебирая все возможные вершины u. Получаем квадратную матрицу d(u,v) = n × n, по которой мы за n² операций находим диаметр и радиус графа.