П.5. Нахождение кратчайших путей. Алгоритм Дейкстры

Едсгер Дейкстра (1930-2002) – нидерландский математик.

В различных приложениях теории графов дугам (рёбрам) графов, моделирующих реальные процессы, обычно сопоставляются какие-либо числовые характеристики. Например, если дугами изображаются транспортные магистрали, то числовой характеристикой дуги может быть пропускная способность соответствующей магистрали и т.п. В таких случаях говорят, что дугам графа приписаны определённые веса.

Пусть ‑ орграф. Если каждой дуге поставлено в соответствие число , то граф называется графом со взвешенными дугами или сетью. При этом вершины графа называют узлами сети. Число называется весом дуги . Весом пути µ (длиной, стоимостью и т.д. в зависимости от контекста) сети называется число .

Понятие сети и веса маршрута для неориентированного графа определяется аналогично.

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

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

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

Определим весовую матрицу Ω чьи элементы задаются формулой

Например, для графа на рис.13 матрица Ω имеет вид:

Матрица Ω является простым обобщением матрицы смежности вершин.

Пусть ‑ ориентированный граф со взвешенными дугами. Обозначим через s ‑ вершину – начало пути, а через t ‑ вершину – конец пути.

В процессе работы алгоритма Дейкстры вершинам графа приписываются числа (метки) , которые служат оценкой длины (веса) кратчайшего пути от вершины s к вершине . Если вершина получила на некотором шаге метку , это означает, что в графе G существует путь из s в , имеющий вес .

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

Ограничения алгоритма Дейкстры – веса должны быть положительными.

Алгоритм состоит из 2-х этапов:

I этап – нахождение длины кратчайшего пути;

II этап – построение кратчайшего пути от вершины s к вершине t.

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