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

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

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

Для любого пути  нагруженного орграфа  обозначим через  сумму длин входящих в  дуг, при этом каждая дуга учитывается столько раз, сколько она входит в путь. Величину  будем называть длиной пути   в нагруженном орграфе . Ранее так называлось количество дуг в пути  . В связи с этим заметим, что если длины дуг выбраны равными 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

	v1	v2	v3	v4	v5	v6
v1	Ґ	Ґ	5	5	2	12		0	0	0	0	0	0
v2	Ґ	Ґ	Ґ	Ґ	Ґ	2		Ґ	Ґ	7	5	5	5
v3	Ґ	2	Ґ	Ґ	Ґ	Ґ		Ґ	5	3	3	3	3
v4	Ґ	2	Ґ	Ґ	Ґ	Ґ		Ґ	5	4	4	4	4
v5	Ґ	Ґ	1	2	Ґ	Ґ		Ґ	2	2	2	2	2
v6	Ґ	Ґ	Ґ	Ґ	Ґ	Ґ		Ґ	12	12	9	7	7

Получаем, что в качестве такой последовательности надо взять номера 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_кон.

Экзамен проводиться письменно.

Предлагаемые практические задания на экзамене составлены в соответствии с теоретическими вопросами. На экзамене можно иметь с собой калькулятор.