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

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

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

Алгоритм решения этой задачи, как и предыдущий, состоит в вычислении по определенным правилам индексов вершин. Индекс вершины обозначим . После окончания процесса вычисления индексов они должны удовлетворять условиям оптимальности, которые заключаются в следующем:

1^°. .

2^°. .

3^°. , где – смежная с вершина.

При выполнении этих условий длина кратчайшей цепи между вершинами и равна , а сама кратчайшая цепь проходит по таким вершинам

,

для которых , .

Для доказательства этого утверждения построим цепь, используя свойство 3^°. Длина такой цепи равна

.

Покажем, что длина любой другой цепи между вершинами и не меньше, чем .

Пусть

произвольная из таких цепей. В силу свойства 2^°:

Сложив эти неравенства, получим

.

Рассмотрим далее алгоритм Дейкстры, который обеспечивает присвоение вершинам графа отметок, удовлетворяющих условиям 1^°–3^°.

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

1) инициализация алгоритма, которая заключается в начальной расстановке отметок;

2) циклически повторяющаяся процедура исправления отметок.

На каждом шаге алгоритма все отметки делятся на предварительные и окончательные. Алгоритм обрабатывает только предварительные отметки и заканчивает работу, когда все отметки станут окончательными.

Рассмотрим алгоритм Э. Дейкстры, который позволяет определить расстояние от одной из вершин графа до всех остальных.

Каждой вершине графа поставим в соответствие метку – минимальное известное расстояние от вершины до начальной вершины . Алгоритм работает пошагово – на каждом шаге он «посещает» одну вершину и пытается уменьшить метки. Работа алгоритма завершается, когда все вершены посещены.

Инициализация (начальная расстановка отметок). Полагаем

.

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

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

.

Объявляем отметку вершины окончательной и повторяем шаг алгоритма для следующей вершины. Число шагов равно числу вершин графа.

Для графа, изображенного на рис. 2, показаны окончательные отметки и кратчайшая цепь.

3 6 5 2 9

8 8 14

Рис. 2. Окончательные отметки и кратчайшая цепь в нагруженном графе