Задача о кратчайших путях
Пусть дан
граф с неотрицательными весами на дугах. Нас будут интересовать две задачи:
1) Какова
длина кратчайшего пути, ведущего из одной выделенной вершины к другой? Каков
этот путь?
2) Каковы
длины кратчайших путей от выделенной вершины до всех остальных вершин графа?
Каковы эти пути?
Задачи 1) и
2) очень похожи, и решение задачи 1) получается в результате прерывания в
нужном месте решения задачи 2).
Приведенный
ниже алгоритм Дейкстры – один из первых известных динамических алгоритмов – основан
на двух идеях:
– присвоении вершинам графа меток и правиле пересчета меток,
при этом окончательные метки – длины кратчайших путей;
–
экстремальном свойстве кратчайшего пути, состоящем в следующем: если кратчайший
путь из вершины х в вершину у проходит через вершину z, то его отрезок от х до
вершины z – кратчайший
путь от вершины х до вершины z, а его отрезок от z до у –
кратчайший путь от z до у.
Опишем шаги
алгоритма Дейкстры нахождения длин кратчайших путей из вершины s до всех вершин графа.
00.
Начальная установка меток и массивов (метку вершины будем обозначать m(x)):
m(s):=
S:={s}, T:=X\S.
10.
Правило пересчета меток и изменения массивов. Пересчитываются только метки
вершин tÎT, для которых существуют дуги, ведущие из множества S
, (1)
где
– дуга из вершины y в вершину t.
20.
Из вершин, метки которых пересчитались, выбрать вершину t, имеющую наименьшую метку
,
.
30.
Правило выхода из алгоритма. Если
, то переход на 40 , иначе
,
и переход на 10.
Восстановление
кратчайшего пути
Кратчайший
путь от вершины 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 и трассу:
.
![]()
Следует
отметить высокую эффективность алгоритма Дейкстры и его широкую применимость в
окружающем нас мире. Бортовые компьютеры современных автомобилей позволяют
находить трассу кратчайшего пути, и делают это они с помощью алгоритма
Дейкстры. Маршрутизаторы, являющиеся важнейшими элементами глобальной
компьютерной сети Интернет, определяя маршрут доставки сообщения с одного
сервера на другой, используют алгоритм Дейкстры.