3.2.3. Нахождение минимального пути в нагруженном графе

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

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

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

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

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

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

(1)

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

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

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

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

.

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

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

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

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

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

.

Из (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 .