Графы. Минимальные пути (маршруты) в нагруженных орграфах (графах). Алгоритм Форда-Беллмана.

Определение. Назовём орграф нагруженным, если на множестве дуг определена некоторая функция , которую часто называют весовой функцией.

Тем самым и нагруженном орграфе каждой дуге поставлено в соответствие некоторое действительное число . Значение будем называть длиной дуги .

Для любого пути нагруженного орграфа обозначим через сумму длин входящих в дуг, при этом каждая дуга учитывается столько раз, сколько она входит в путь. Величину будем называть длиной пути в нагруженном орграфе . Ранее так называлось количество дуг в пути . В связи с этим заметим, что если длины дуг выбраны равными 1, то выражает введенную ранее длину пути в ненагруженном орграфе. Следовательно, любой ненагруженный орграф можно считать нагруженным с длинами дуг, равными 1. Аналогично определяется и нагруженный граф, а также длина маршрута в нем.

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

Рассмотрим теперь задачу поиска минимальных путей (маршрутов) в нагруженном орграфе (графе). При этом для определенности рассуждения будем проводить для орграфа (для графа они аналогичны).

Пусть - нагруженный орграф, , . Введем величины , где , ..., , , ,... Для каждых фиксированных и величина равна длине минимального пути среди путем из в , содержащих не более дуг; если же таких путей нет, то = . Кроме того, если произвольную вершину считать путем из в нулевой длины, то величины можно ввести также и для , при этом

(1)

Введем также в рассмотрение квадратную матрицу порядка с элементами

которую будем называть матрицей длин дуг нагруженного орграфа .

Следующее утверждение дает простые формулы для вычисления величин .

Утверждение.

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

Алгоритм Форда – Беллмана нахождения минимального пути в нагруженном орграфе из в

Шаг 1. Пусть мы уже составили таблицу величин . Если не достижима из (предполагаем, что все величины конечны). В этом случае работа алгоритма заканчивается.

Шаг 2. Пусть . Тогда число выражает длинны любого минимального пути из в в нагруженном орграфе . Определим минимальное число , при котором выполняется равенство . По определению чисел получим, что - минимальное число дуг в пути среди всех минимальных путей из в в нагруженном орграфе .

Шаг 3. Последовательно определяем номера такие что

. . . . . . (4)

Из (4) с учётом того, что , имеем , откуда, используя (1), получаем

(5)

Складывая равенства (4) и учитывая (5), имеем

т.е. - искомый минимальный путь из в в нагруженном орграфе . Заметим, что в этом пути ровно дуг Следовательно, мы определили путь с минимальным числом дуг среди всех минимальных путей из в в нагруженном орграфе .

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

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

Пример 83.

Определить минимальный путь из v1 в v6 в нагруженном орграфе D, изображенном на рисунке 35.

Решение.

Составим матрицу C(D) длин дуг нагруженного орграфа D(табл. 68). Справа от матрицы C(D) припишем шесть столбцов, которые будем определять, используя рекуррентное соотношение (2) и исходя из (1).

Величина выражает длину минимального пути из v1 в v6 в нагруженном орграфе D. Найдем минимальное число , при котором выполняется равенство . Получаем, что k1 = 4. Таким образом, минимальное число дуг в пути среди всех минимальных путей из v1 в v6 в нагруженном графе D равняется 4. Определим теперь последовательность номеров i1, i2, i3, i4, i5, где i1 = 6, удовлетворяющих (4) (для этого используем формулу (2)).

Таблица 68

Получаем, что в качестве такой последовательности надо взять номера 6, 2, 3, 5, 1, так как

Тогда v1v5v3v2v6 – искомый минимальный путь из v1 в v6 в нагруженном орграфе D, причем он содержит минимальное число дуг среди всех возможных минимальных путей из v1 в v6 .

Алгоритм Форда-Беллмана нахождения минимального пути в нагруженном ориентированном графе D из v_нач в v_кон.( v_нач ≠ v_кон)

записываем в виде матрицы, i- строка, k-столбец.

1) Составляем таблицу , i=1,…,n, k=0,…,n-1. Если , то пути из v_нач в v_кон нет. Конец алгоритма.

2) Если то это число выражает длину любого минимального пути из v_нач в v_кон. Найдем минимальное k₁1, при котором . По определению получим, что k₁- минимальное число дуг в пути среди всех минимальных путей из v_нач в v_кон.

3) Затем определяем номера i₂,…, такие, что

то есть, восстанавливаем по составленной таблице и матрице стоимости искомый минимальный путь из v_нач в v_кон.