2. Минимальные пути в нагруженных орграфах

Орграф D(V, X) называется нагруженным, если на множестве дуг X определена функция, называемая весовой, ставящая в соответствие каждой дуге некоторое действительное число l(x). Значение l(x) будем называть длиной дуги х.

Обозначим какой-либо путь в орграфе D через , тогда l() – длина этого пути, равная сумме длин входящих в  дуг. Заметим, что если длины всех дуг в орграфе равны 1, то длина любого пути будет равна числу дуг в этом пути. Таким образом, можно считать ненагруженный орграф нагруженным с длинами дуг, равными 1.

Путь в нагруженном орграфе D из вершины v в вершину w (v  w) называется минимальным, если он имеет минимальную длину среди всех путей орграфа D из v в w.

Длины дуг могут быть как положительными, так и отрицательными. Рассмотрим только такие орграфы, длины дуг которых есть числа l(x) > 0.

Приведем некоторые свойства минимальных путей в нагруженных орграфах:

1. если для любой х Х l(x) > 0, то любой минимальный путь является простой цепью;

2. если v₁v₂…v_k – минимальный путь, то для любых номеров i и j таких, что 1 i j k , путь v_i v_i+1…v_j также – минимальный;

3. если v…uw – минимальный путь среди путей из v в w, содержащих не более k + 1 дуг, то v..u – минимальный путь среди путей из v в u , содержащих не более k дуг.

Рассмотрим теперь задачу поиска минимальных путей в орграфах.

Пусть D(V, X) – нагруженный орграф, n  2. Введем величины _i^k , где i = 1, …, n, k = 1, 2…Для каждых фиксированных i и k величина _i^k равна длине минимального пути среди всех путей из v₁ в v_i (v₁ - начало пути), содержащего k дуг. Если таких путей нет, то _i^k = . Если произвольную вершину v считать путем из v в v нулевой длины, то величины _i^k можно ввести для k = 0, при этом ₁⁰ = 0, _i⁰ = , i = 2,…,n.

Введем также квадратную матрицу С(D) = [c_ij], порядка n, называемую матрицей длин дуг:

l(v_i, v_j) – длина дуги (v_i, v_j).

Для вычисления _i^k используем формулы:

При i = 2, …,n, k  0 выполняется равенство:

_i^k+1 = min{_j^k + c_ji},

1 j  n

где _j^k – это величины всех вершин кроме i- ой, c_ji – это длины дуг из каждой j – ой вершины в i – ую, для которой вычисляется _i^k+1.

при i = 1, k  0 верно равенство:

₁^k+1 = min{0; min{_j^k + c_j1}, если нет дуг отрицательной длины, то ₁^k+1 = 0.

1 j  n

Приведем алгоритм, позволяющий по таблице величин _i^k , i = 1, 2,…,n, k = 0, 1, …, n – 1, определить минимальный путь в нагруженном графе D из v1 в любую достижимую вершину, причем алгоритм выделяет путь с наименьшим числом дуг.

Алгоритм носит название алгоритма Форда – Беллмана.

Шаг1. Пусть составлена таблица величин _i^k , i = 1, 2,…,n, k = 0, 1, …, n – 1. Если _i1^n-1 = , то вершина v_i1 не достижима из v₁. Работа алгоритма заканчивается.

Шаг2. Пусть _i1^n-1< , тогда число _i1^n-1 выражает длину минимального пути из вершины v₁ в вершину v_i1. Определим минимальное число дуг k₁  1, при котором выполняется равенство _i1^k1 = _i1^n-1. Получаем, что k₁ - минимальное число дуг в минимальном пути.

Шаг3. Последовательно определим номера вершин в этом пути i₂, … , i_k1+1:

_i2^k1-1 + c_{i2, i1} = _i1^k1;

_i3^k1-2 + c_{i3, i2} = _i2^k1-1;

………………………

_ik1+1⁰ + c_ik1+1 = _ik1¹.

Пример:

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

Составим матрицу длин дуг графа и рядом таблицу величин _i^k, содержащую шесть столбцов k = 0, 1, …, 5, используя соотношения:

При i = 2, …,n, k  0 выполняется равенство

_i^k+1 = min{_j^k + c_ji},

1 j  n

при i = 1, k  0 верно равенство

₁^k+1 = min{0; min{_j^k + c_j1},

1 j  n

Первый столбец значений _i^k : ₁⁰= 0 (начало пути), остальные - . Вся первая строка содержит нули, т.к. это начало пути и 0 – наименьшая длина из v₁ в v₁.

Второй столбец: _i¹ – это длины дуг , соединяющих v₁ с другими вершинами и , начиная со второй вершины , заносим значения из первой строки матрицы длин дуг.

Третий столбец: ₂² = min{0+, 5+2, 5+2, 2+, 12+}= 7;

₃² = min {0+5, +, 5+, 2+1, 12+}=3;

₄² = min{0+5, +, 5+, 2+2,12+}= 4;

₅² = min{0+2, +,5+,5+,12+} = 2;

₆² = min{0+12, +2,5+,5+,2+} = 12.

Четвертый столбец:

₂³ = min{0+, 3+2, 4+2, 2+, 12+}= 5;

₃³ = min {0+5, 7+, 4+, 2+1, 12+}=3;

₄³ = min{0+5, 7+, 3+, 2+2,12+}= 4;

₅³ = min{0+2, 7+,3+,4+,12+} = 2;

₆³ = min{0+12, 7+2,3+,4+,2+} = 9.

Пятый столбец:

₂⁴ = min{0+, 3+2, 4+2, 2+, 9+}= 5;

₃⁴ = min {0+5, 5+, 4+, 2+1, 9+}=3;

₄⁴ = min{0+5, 5+, 3+, 2+2,9+}= 4;

₅⁴ = min{0+2, 5+,3+,4+,9+} = 2;

₆⁴ = min{0+12, 5+2,3+,4+,2+} = 7.

Последний шестой столбец:

₂⁵ = min{0+, 3+2, 4+2, 2+, 7+}= 5;

₃⁵ = min {0+5, 5+, 4+, 2+1, 7+}=3;

₄⁵ = min{0+5, 5+, 3+, 2+2,7+}= 4;

₅⁵ = min{0+2, 5+,3+,4+,7+} = 2;

₆⁵ = min{0+12, 5+2,3+,4+,2+} = 7.

Итак, минимальный путь из v₁ в v₆ равен 7 и содержит 4 дуги, т.к. первый раз 7 появилось в столбце _i⁴, т.е. для вершины v₆ ₆⁴ = 7.

Найдем последовательность вершин, входящих в этот путь:

₆⁴ = 7= ₂³ + с₂₆ =5+2;

₂³ = 5 = ₃² + с₃₂ = 3+2;

₃² = 3 = ₅¹ + с₅₃ = 2+1;

₅¹ = ₁⁰ + с₁₅ = 0+2.

Получили путь v₁v₅v₃v₂v₆ .