Алгоритм Беллмана

Алгоритм Беллмана решения задачи о кратчайшем пути. Алгоритм Флойда отыскания кратчайших путей между всеми парами вершин графа

Алгоритм Беллмана

Алгоритм определяет длины кратчайших путей от фиксированной вершины s до всех остальных вершин графа. Он корректно работает с дугами отрицательной длины и, в случае присутствия в графе контура отрицательной длины, обнаруживает его и сообщает о невозможности построения кратчайших путей.

Заметим, что всякий кратчайший путь – это простая цепь, поэтому в любом кратчайшем пути в графе G с множеством вершин { s, v ₁, v ₂, … v_n } не более n дуг.

Обозначим через – длину пути от вершины s до вершины v_i, кратчайшего из всех путей от s до v_i, в которых не более k дуг.

Тогда

(1)

. (2)

Здесь – это длина пути до вершины v_i, предпоследняя вершина которого – v_j. Причем путь до v_j – кратчайший из всех путей до этой вершины, в которых не более чем k дуг.

Зная числа , , можно шаг за шагом рассчитать числа ,..., , . Если задача о кратчайшем пути имеет решение, величины , - это заведомо длины кратчайших путей от вершины s до вершин v ₁, v ₂, …, v_n.

Чтобы определить, есть ли в графе G контур отрицательной длины, нужно рассчитать числа , . Если окажется, что хотя бы одно из этих чисел меньше соответствующего значения предыдущего шага, в графе есть контур отрицательной длины: путь от вершины s до некоторой вершины v, содержащий n+ 1 дугу оказался короче пути от s до v, состоящего из n дуг.

Алгоритм может окончить работу быстрее, чем за n шагов. Не обязательно, чтобы в графе существовали кратчайшие пути, содержащие n дуг. Если все числа , , найденные на шаге совпадают с соответствующими величинами, определенными на k- м шаге, то кратчайшие пути найдены, а максимальное число дуг в кратчайших путях равно k.

Пример 1. Определим кратчайшие пути от вершины 1 до всех остальных вершин графа, изображенного на рис. 1. В графе есть дуги отрицательной длины, поэтому применим алгоритмом Беллмана.

И здесь удобно воспользоваться таблицей (табл. 1).Столбцы таблицы соответствуют вершинам графа. В k- й строке таблицы стоят числа , . Первый столбец таблицы соответствует вершине s (вершине 1), он содержит одни нули.

На первом шаге находятся пути из одной дуги до вершин 2, 4, 5. Значит, пути, состоящие не более чем из двух дуг, следует искать только до вершин, в которые входят дуги выходящие из вершин 2, 4, 5 (рис. 2).

Над кружками с номерами вершин на рис. 2 стоят длины путей до этих вершин, найденные на предыдущем шаге.

;

;

;

;

;

;

; .

Заполним вторую строку табл. 1.

Таблица 1

Уменьшились длины путей до вершин 2, 3, 6, 7, 8, 9. Значит, имеет смысл искать более короткие пути до тех вершин графа, в которые входят дуги из перечисленных вершин (рис. 3).

; ;

;

;

; ;

.

Заполняем третью строку табл. 1. На третьем шаге уменьшились длины путей до вершин 3, 5, 6, 8, 9. Постараемся найти более короткие пути до

тех вершин графа, в которые входят дуги, выходящие из перечисленных вершин (рис. 4).

; ;

;

; ;

; .

Заполняем четвертую строку таблицы. Уменьшились длины путей до вершин 3, 5, 8, 9. Продолжаем действовать по алгоритму Беллмана (рис. 5).

;

;

;

;

;

; .

Заполняем пятую строку таблицы. Уменьшились длины путей до вершин 3, 5, 9. Следовательно, нужно пересчитать длины путей до вершин 2, 3, 4, 5, 6, 7, 9.

; ;

; ;

; ;

.

Заполняем шестую строку таблицы. Уменьшилась длина пути до вершины 3. Нужно пересчитать длины путей до вершин 2, 5, 6.

; ; .

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

Построим дерево кратчайших путей (рис. 6). Длина кратчайшего пути до вершины 4 была найдена уже в первой строке. Значит, этот путь состоит из одной дуги. Включаем в дерево дугу (1, 4). Во второй строке стоят длины кратчайших путей до вершин 2 и 7. Следовательно, эти пути включают в себя две дуги. Из расчетов (и диаграммы) вытекает, что предпоследняя вершина кратчайшего пути как до вершины 2, так и до вершины 7 – это вершина 4. В дерево кратчайших путей добавляем дуги (4, 2) и (4, 7).

В третьей строке табл. 1 стоит длина кратчайшего пути до вершины 6, этот путь состоит из трех дуг. Пользуясь расчетами (и диаграммой) находим, что кратчайший путь до вершины 6 – это путь 1-4-2-6. Включаем в дерево дугу (2, 6). Продолжая анализ табл. 1, достраиваем дерево кратчайших путей.

Пример 2. Покажем, как алгоритм Беллмана обнаруживает контур отрицательной длины.

На рис. 7 изображен граф, для которого задача о кратчайшем пути не имеет решения из-за присутствия контура 2-3-4-2 длины -1. Из-за него длины путей от вершины 1 до всех остальных вершин графа можно сделать как угодно большими по модулю, но отрицательными по знаку.

Для этого достаточно обойти контур 2-3-4-2 нужное число раз.

Без дальнейших пояснений приведем таблицу алгоритма Беллмана (табл. 2).

В четвертой строке табл. 2 уменьшилась

длина пути до второй вершины. Путь из

четырех дуг 1-2-3-4-2 оказался короче пути

из одной дуги (1, 2). Алгоритм обнаружил в графе контур отрицательной длины.

,