2. Нахождение кратчайших путей. Алгоритм Беллмана-Мура

Веса дуг могут быть и отрицательными.

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

Шаг 1. Присвоение начальных значений. - множество вершин в очереди.

Шаг 2. Корректировка меток и очереди.

Удаляем из очереди Q вершину, находящуюся в самом начале очереди. Для каждой вершины х_i, непосредственно достижимой из , корректируем её метку по формуле

.

Если при этом , то корректируем очередь вершин, иначе продолжаем перебор вершин и корректировку временных меток.

Корректировка очереди. Если х_i не была ранее в очереди и не находится в ней в данный момент, то ставим её в конец очереди. Если х_i уже была когда-нибудь ранее в очереди или находится там в данный момент, то переставим её в начало очереди.

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

Если , то возвращаемся к началу 2-го шага; если же , то 1-ый этап закончен, т.е. минимальное расстояние от s до всех вершин графа найдены.

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

Совпадает с соответствующим этапом в алгоритме Дейкстры и выполняется по формуле

Пример. Задана весовая матрица Ω сети G:

Рис. 35

Рассчитать кратчайший путь от узла х₁ до узла х₆.

Решение.

Этап 1. Первая итерация.

Шаг 1.

Шаг 2. множество вершин непосредственно достижимых из вершины .

х₂ надо было поставить в конец очереди, но Q было пусто, поэтому конец очереди совпал с началом.

Шаг 3. Нет. Переход на начало 2-го шага.

Вторая итерация.

Шаг 2.

Вершину х₄ надо поставить в начало очереди, но она уже стоит там.

Шаг 3. Нет, переход на третью итерацию 2 –го шага.

Третья итерация.

Шаг 2.

Вершину х₃ надо ставить в начало очереди, но она уже там.

Вершину х₅ передвигаем из конца очереди в начало.

Шаг 3. Нет, переход на четвёртую итерацию 2 –го шага.

Четвёртая итерация.

Шаг 2.

Шаг 3. Нет.

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

Шаг 2.

Шаг 3. Нет.

Шестая итерация.

Шаг 2.

Q содержало только вершину x₆ и она встала в начало очереди.

Шаг 3. Нет.

Седьмая итерация.

Шаг 2.

Шаг 3. Конец 1-го этапа. Найдены минимальные расстояния до всех вершин от первой. Эти расстояния таковы:

Этап 2.

Шаг 4. Полагаем . Пусть - множество вершин, непосредственно предшествующих . .

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

или

Включаем дугу (х₅, х₆) в кратчайший путь. . Возвращаемся на 4-ый шаг.

Вторая итерация. Нет.

; ,

.

Включаем дугу (х₃, х₅) в кратчайший путь. .Возвращаемся на 4-ый шаг.

Третья итерация. Нет.

.

. Включаем дугу (х₄, х₃) в кратчайший путь. . Возвращаемся на 4-ый шаг.

Четвёртая итерация. Нет. .

. Включаем дугу (х₂, х₄) в кратчайший путь . Возвращаемся на 4-ый шаг.

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

. Включаем дугу (х₁, х₂) в кратчайший путь . Возвращаемся на 4-ый шаг.

Шестая итерация. Да. Задача закончена. Искомый кратчайший путь от вершины х₁ до вершины х₆ имеет нулевой вес и состоит из следующих дуг: