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

Найти минимальный путь в нагруженном ориентированном графе из вершины в вершину по методу Форда-Беллмана.

Рассмотрим сначала общую задачу – нахождения минимального пути из вершины v_нач в v_кон.

Пусть D =(V, X) – нагруженный ориентированный граф, V ={ v ₁,…, v_n }, n >1. Введем величины , где i =1,…, n, k =0,1,2,…, n– 1.

Для каждого фиксированного i и k величина равна длине минимального пути среди путей из v_нач в v_i содержащих не более k дуг. Если путей нет, то .

Положим также .

Составляем матрицу длин дуг C (D)=[ c_ij ] порядка n:

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

. (3.1)

Алгоритм Форда-Беллмана нахождения минимального пути в нагруженном ориентированном графе 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_кон.

Пример2

Найдем минимальный путь из вершины v ₂ в v ₆ в ориентированном нагруженном графе D, изображенном на рис. 9. В рассматриваемом графе количество вершин n= 7, следовательно, матрица длин дуг ориентированного графа D будет иметь размерность 7×7.

Рис. 9.

Матрица длин дуг для рассматриваемого графа будет выглядеть следующим образом:

.

Согласно алгоритму, составляем таблицу стоимости минимальных путей из вершины v ₂ в вершину v_i не более, чем за k шагов, k =0,… n -1 (n =7, следовательно, k =0,…6). Как было определено выше, , и для всех остальных вершин v_i ≠ v ₂, то есть первый столбец таблицы состоит из элементов, равных , кроме элемента . Второй столбец таблицы повторяет вторую строку матрицы стоимости, поскольку представляет собой стоимость возможных путей из вершины v ₂ за один шаг. Далее по формуле (3.1) находим по столбцам все оставшиеся элементы таблицы. Например, чтобы найти элемент , складываем элементы столбца и первого столбца матрицы стоимости и выбираем минимальное из получившихся чисел: .

В конечном итоге получаем следующую таблицу:

Теперь необходимо по построенной таблице и по матрице C (D) восстановить минимальный путь из вершины v ₂ в v ₆, который будет строиться с конца, то есть, начиная с вершины v 6. Для этого выбираем минимальное из чисел, стоящих в строке, соответствующей v ₆ в таблице. Это число – 21 – длина минимального искомого пути. В первый раз такая длина была получена при количестве шагов, равном 4. В вершину v ₆ мы можем попасть за один шаг из вершин v ₁ и v ₇ (длина соответствующих дуг 8 и 5 соответственно – данные из матрицы C (D)). Выбираем минимальную по длине из этих дуг. Далее, в вершину v ₇ можно попасть из v ₄ и v ₅(длина соответствующих дуг 7 и 3 соответственно). Продолжая аналогичным образом, найдем искомый путь за 4 шага минимальной длины из вершины v ₂ в v ₆: v ₂ v ₃ v ₅ v ₇ v ₆.