Первая итерация.

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

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

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

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

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

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

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

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

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

.

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

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

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

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

.

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

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

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

Пример. Задана весовая матрица Ω сети G. Найти минимальный путь из вершины в вершину по алгоритму Дейкстры.

По данной матрице весов граф изображён на рис.14:

В данном графе есть цикл . Поэтому вершины графа нельзя упорядочить по алгоритму Фалкерсона.

Распишем подробно работу алгоритма Дейкстры.

Шаг 1. ,

, , , , .

Шаг 2. Множество вершин непосредственно следующих за с временными метками . Пересчитываем временные метки этих вершин:

;

;

.

Шаг 3. Одна из временных меток превращается в постоянную:

Следовательно, .

Шаг 4. , происходит возвращение на второй шаг.