double arrow

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


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

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

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

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

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

    1. если для любой хÎ Х l(x) > 0, то любой минимальный путь является простой цепью;
    2. если v1v2…vk – минимальный путь, то для любых номеров i и j таких, что 1£ i£ j£ k , путь vi vi+1…vj также – минимальный;
    3. если v…uw – минимальный путь среди путей из v в w, содержащих не более k + 1 дуг, то v..u – минимальный путь среди путей из v в u , содержащих не более k дуг.

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




Пусть D(V, X) – нагруженный орграф, n ³ 2. Введем величины lik , где i = 1, …, n, k = 1, 2…Для каждых фиксированных i и k величина lik равна длине минимального пути среди всех путей из v1 в vi (v1 - начало пути), содержащего k дуг. Если таких путей нет, то lik = ¥. Если произвольную вершину v считать путем из v в v нулевой длины, то величины lik можно ввести для k = 0, при этом l10 = 0, li0 = ¥, i = 2,…,n.

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

l(vi, vj) – длина дуги (vi, vj).

Для вычисления lik используем формулы:

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

lik+1 = min{ljk + cji},

1£ j £ n

где ljk – это величины всех вершин кроме i- ой, cji – это длины дуг из каждой j – ой вершины в i – ую, для которой вычисляется lik+1.

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

l1k+1 = min{0; min{ljk + cj1}, если нет дуг отрицательной длины, то l1k+1 = 0.

1£ j £ n

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

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

Шаг1. Пусть составлена таблица величин lik , i = 1, 2,…,n, k = 0, 1, …, n – 1. Если li1n-1 = ¥, то вершина vi1 не достижима из v1. Работа алгоритма заканчивается.

Шаг2. Пусть li1n-1< ¥, тогда число li1n-1 выражает длину минимального пути из вершины v1 в вершину vi1. Определим минимальное число дуг k1 ³ 1, при котором выполняется равенство li1k1 = li1n-1. Получаем, что k1 - минимальное число дуг в минимальном пути.



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

li2k1-1 + ci2, i1 = li1k1;

li3k1-2 + ci3, i2 = li2k1-1;

………………………

lik1+10 + cik1+1 = lik11.

Пример:

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

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

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

lik+1 = min{ljk + cji},

1£ j £ n

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

l1k+1 = min{0; min{ljk + cj1},

1£ j £ n

  V1 V2 V3 V4 V5 V6   li0 li1 li2 li3 li4 li5
V1 ¥ ¥  
V2 ¥ ¥ ¥ ¥ ¥   ¥ ¥
V3 ¥ ¥ ¥ ¥ ¥   ¥
V4 ¥ ¥ ¥ ¥ ¥   ¥
V5 ¥ ¥ ¥ ¥   ¥
V6 ¥ ¥ ¥ ¥ ¥ ¥   ¥

Первый столбец значений lik : l10= 0 (начало пути), остальные - ¥. Вся первая строка содержит нули, т.к. это начало пути и 0 – наименьшая длина из v1 в v1.

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

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

l32 = min {0+5, ¥+¥, 5+¥, 2+1, 12+¥}=3;

l42 = min{0+5, ¥+¥, 5+¥, 2+2,12+¥}= 4;

l52 = min{0+2, ¥+¥,5+¥,5+¥,12+¥} = 2;



l62 = min{0+12, ¥+2,5+¥,5+¥,2+¥} = 12.

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

l23 = min{0+¥, 3+2, 4+2, 2+¥, 12+¥}= 5;

l33 = min {0+5, 7+¥, 4+¥, 2+1, 12+¥}=3;

l43 = min{0+5, 7+¥, 3+¥, 2+2,12+¥}= 4;

l53 = min{0+2, 7+¥,3+¥,4+¥,12+¥} = 2;

l63 = min{0+12, 7+2,3+¥,4+¥,2+¥} = 9.

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

l24 = min{0+¥, 3+2, 4+2, 2+¥, 9+¥}= 5;

l34 = min {0+5, 5+¥, 4+¥, 2+1, 9+¥}=3;

l44 = min{0+5, 5+¥, 3+¥, 2+2,9+¥}= 4;

l54 = min{0+2, 5+¥,3+¥,4+¥,9+¥} = 2;

l64 = min{0+12, 5+2,3+¥,4+¥,2+¥} = 7.

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

l25 = min{0+¥, 3+2, 4+2, 2+¥, 7+¥}= 5;

l35 = min {0+5, 5+¥, 4+¥, 2+1, 7+¥}=3;

l45 = min{0+5, 5+¥, 3+¥, 2+2,7+¥}= 4;

l55 = min{0+2, 5+¥,3+¥,4+¥,7+¥} = 2;

l65 = min{0+12, 5+2,3+¥,4+¥,2+¥} = 7.

Итак, минимальный путь из v1 в v6 равен 7 и содержит 4 дуги, т.к. первый раз 7 появилось в столбце li4, т.е. для вершины v6 l64 = 7.

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

l64 = 7= l23 + с26 =5+2;

l23 = 5 = l32 + с32 = 3+2;

l32 = 3 = l51 + с53 = 2+1;

l51 = l10 + с15 = 0+2.

Получили путь v1v5v3v2v6 .







Сейчас читают про: