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