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

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

1. Какова длина кратчайшего пути, ведущего из одной вершины в другую? Каков этот путь?
2. Каковы длины кратчайших путей от выделенной вершины до всех остальных вершин графа?

Алгоритм, который будет описан, называется алгоритмом Дейкстры. Дейкстра Еусгер родился в 1930 году в Нидерландах. Считается одним из основоположников программирования как учебной дисциплины. С 1984 года работает в Техасе.

Согласно алгоритму отыскивается кратчайшее расстояние от вершины v₀ к вершине z простого взвешенного графа G(V, E). Если граф не является простым, то его можно сделать таковым, отбрасывая все петли заменяя каждое множество параллельных ребер кратчайшим ребром (ребром с наименьшим весом). Обозначим через w_{i j} - вес ребра (v_i, v_j). Начинаем от вершины v₀ и просматриваем граф в ширину, помечая вершины v_i значениями-метками их расстояний от v₀. Метки могут быть временными или окончательными

Временная метка вершины v_j – это минимальное расстояние от вершины v₀ до вершины v_j, когда в определении пути на графе учитываются не все маршруты из v₀ в v_j.

Окончательная метка – это минимальное расстояние от вершины v₀ до вершины v_j. Таким образом, в каждый момент времени работы алгоритма некоторые вершины будут иметь окончательные метки, а некоторые – временные. Алгоритм заканчивается, когда вершина v_n получит окончательную метку, т.е. расстояние от v₀ до z..

Каждой вершине v_k присваивается упорядоченная пара (m(v_k), v_r). Первая координата этой пары является меткой вершины v_k, а вторая координата – предыдущую вершину пути от v₀ к v_k.

Вначале вершине v₀ присваивается окончательная метка 0 (нулевое расстояние до самой себя), а каждой из остальных вершин присваивается временная метка ∞. На каждом шаге одной вершине с временной меткой присваивается окончательная и поиск продолжается дальше. На каждом шаге метки меняются следующим образом:

1. Когда вершина v_k получит постоянную метку m(v_k) каждой вершине vj, смежной к v_k, присваивается новая временная метка m(v_j), равная минимуму между ее старой временной меткой и числом (w_{k j} + m(v_k)).

2. Смежная с v_k вершина, получившая наименьшую временную метку, делается постоянной (имеет постоянную метку).

3. Если вершина z не имеет постоянной метки, то возвращаемся к пункту 1.

4. Если z имеет постоянную метку m(z), то эта метка является кратчайшим расстоянием от v₀ к z

5. Для нахождения пути надо рассмотреть постоянные метки в обратном направлении от z к v₀.

П р и м е р 1.

 

Рассмотрим пример варианта поиска кратчайшего пути поиска кратчайшего пути на графе, представленном на рисунке.

. 10 z

5 2

v₁ v₄

7 1 8 3 6

3 3 5

 

 

v₀ 2 v₂ 5 v₃ 7 v₅

 

 

Процесс назначения меток вершинам графа на каждом шаге представляется в виде таблицы.

 

 

 

Рамочками выделены окончательные метки, т.е. расстояние от них до v₀ ( вторая координата – номер предыдущей вершины). По такой таблице легко восстановить путь перемещения от v₀ к z и обратно. Кратчайшим путем является перемещение v₀, v₂, v₁, v₃, v₄, z. Кратчайшее расстояние равно 11.

 

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

П р и м е р 2 .

Для графа, приведенного на рисунке, найти длины кратчайших путей от вершины v₀ ко всем остальным и восстановить кратчайший путь от v₀ к v₆.

v₁1 v₈ 1 v₇

1 1 1

v₀ v₆

v₂1 v₃ 2

24 3

v₄ 1 v₅

 

Кратчайший путь от v₀ в v₇ имеет следующий вид .Это расстояние равно 4. Путь через вершину v₂ более длинный и равен %

Нижние постоянные метки дают кратчайшее расстояние от v₀ до соответствующей вершины.