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

Этап 1. Нахождение длины кратчайшего пути.

Шаг 1. Присвоение вершинам начальных меток.

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

Шаг 2. Изменение меток.

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

.

Шаг 3. Превращение временной метки в постоянную.

Из всех вершин с временными метками выбираем вершину с наименьшим значением метки

где − временная метка.

Превращаем эту метку в постоянную и полагаем .

Шаг 4. Проверка на завершение первого этапа.

Если , то – длина кратчайшего пути от вершины до . В противном случае происходит возвращение ко второму шагу.

Этап 2. Построение кратчайшего пути.

Шаг 5. Последовательный поиск дуг кратчайшего пути.

Среди вершин, непосредственно предшествующих вершине с постоянными метками, находим вершину , удовлетворяющую соотношению

.

Включаем дугу в искомый путь и полагаем .

Шаг 6. Проверка на завершение второго этапа.

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

Пример 3.1. По заданной матрице весов

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

Решение.

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

Этап 1. Шаг 1. Полагаем ,

.

Шаг 2. За вершиной следуют вершины, которые образуют множество .

Пересчитаем временные метки:

, ,

, .

Получаем . Следовательно, вершине присваивается постоянная метка: , .

Шаг 3. . Пересчитаем временные метки:

, ,

, .

Получаем . Следовательно, вершине присваивается постоянная метка: , .

Шаг 4. . Пересчитаем временные метки:

, ,

, .

Получаем . Следовательно, вершине присваивается постоянная метка: .

Шаг 5. . Пересчитаем временные метки:

,

,

.

Получаем . Следовательно, вершинам и присваиваются постоянные метки: .

Шаг 6. . Вершине присваивается постоянная метка .

Этап 2.

Проводим последовательный поиск дуг кратчайшего пути.

Вершине предшествуют вершины . Кратчайшее расстояние получим при прохождении по дуге

Вершине предшествуют вершины . Кратчайшее расстояние получием при прохождении по дуге

Таким образом, кратчайший путь от вершины до вершины построен. Его длина (вес) составляет 21, т.е. , сам путь задает следующую последовательность дуг –

Ответ: , –

4. ЭЙЛЕРОВЫ И ГАМИЛЬТОНОВЫ ЦИКЛЫ