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

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

Рассмотрим сначала общую задачу – нахождения минимального пути из вершины 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 _кон.

Пример

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