Задача о кратчайших путях

 

Пусть дан граф с неотрицательными весами на дугах. Нас будут интересовать две задачи:

1) Какова длина кратчайшего пути, ведущего из одной выделенной вершины к другой? Каков этот путь?

2) Каковы длины кратчайших путей от выделенной вершины до всех остальных вершин графа? Каковы эти пути?

Задачи 1) и 2) очень похожи, и решение задачи 1) получается в результате прерывания в нужном месте решения задачи 2).

Приведенный ниже алгоритм Дейкстры – один из первых известных динамических алгоритмов – основан на двух идеях:

– присвоении вершинам графа меток и правиле пересчета меток, при этом окончательные метки – длины кратчайших путей;

– экстремальном свойстве кратчайшего пути, состоящем в следующем: если кратчайший путь из вершины х в вершину у проходит через вершину z, то его отрезок от х до вершины z – кратчайший путь от вершины х до вершины z, а его отрезок от z до у – кратчайший путь от z до у.

Опишем шаги алгоритма Дейкстры нахождения длин кратчайших путей из вершины s до всех вершин графа.

00. Начальная установка меток и массивов (метку вершины будем обозначать m(x)):

m(s):= 0, m(x):= ¥ для всех х ¹ s;

S:={s}, T:=X\S.

10. Правило пересчета меток и изменения массивов. Пересчитываются только метки вершин tÎT, для которых существуют дуги, ведущие из множества S

,                               (1)

где  – дуга из вершины y в вершину t.

20. Из вершин, метки которых пересчитались, выбрать вершину t, имеющую наименьшую метку

, .

30. Правило выхода из алгоритма. Если , то переход на 40 , иначе ,  и переход на 10.

40. m(x) – длина кратчайшего пути из вершины s в вершину х, если m(x)=¥, то пути из вершины s в вершину х на графе не существует.

 

Восстановление кратчайшего пути

 

Кратчайший путь от вершины s к вершине t восстанавливается по известным меткам вершин, полученным с помощью алгоритма Дейкстры, пощагово от вершины t до возврата в вершину s. Восстановление основано на экстремальном свойстве кратчайшего пути. Опишем один шаг возвращения.

Для вершины t среди вершин  найти такую, для которой выполнено условие:

                       (2)

Условие (2) восстанавливает последнюю дугу кратчайшего пути . После чего выполняется шаг возвращения от вершины у и т.д.

Пример. Для графа, приведенного на рис.1, найти длины кратчайших путей от вершины х1 ко всем остальным и восстановить кратчайший путь от х1 к х7 (числа около дуг – их веса).

 

 

Рис. 1

 

 Решение задачи сведем в таблицу 1 (окончательные метки заключены в скобки).

Проведем восстановление пути из х1 к х7. Ясно, что

,

,

,

.

 

Таблица 1:

 

№ шага пересчета меток

Метки вершин

х1

х2

х3

х4

х5

х6

х7

х8

х9

0

1

2

3

4

5

(0)

0

0

0

0

0

¥

(1)

1

1

1

1

¥

3

(2)

2

2

2

¥

¥

4

(3)

3

3

¥

(2)

2

2

2

2

¥

4

(3)

3

3

3

¥

¥

7

6

(4)

4

¥

¥

4

(3)

3

3

¥

¥

(2)

2

2

2

 

Таким образом, кратчайший путь из х1 к х7 имеет длину 4 и трассу:

.

Следует отметить высокую эффективность алгоритма Дейкстры и его широкую применимость в окружающем нас мире. Бортовые компьютеры современных автомобилей позволяют находить трассу кратчайшего пути, и делают это они с помощью алгоритма Дейкстры. Маршрутизаторы, являющиеся важнейшими элементами глобальной компьютерной сети Интернет, определяя маршрут доставки сообщения с одного сервера на другой, используют алгоритм Дейкстры.