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

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

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

Путь в орграфе G из вершины U в вершину Vназывается минимальным, если он имеет минимальную длину среду всех путей ведущих из U в V. Минимальный путь в нагруженном орграфе определяется также, как и в обыкновенном орграфе.

Алгоритм Форда-Беллмана:

i – номер строки, k+1 – номер столбца.

1. Если =∞ => не существует min пути из V₁ в V_i, V_i не достижимо из V_1, в это случае работа алгоритма прекращается, в противном случае →2.

2. Пусть <∞, тогда число представляет собой длину min пути из V₁ в V_i достигаемого за ≤n-1 дугу, определяющего количество дуг минимального пути – это есть min значение k, при котором выполняется равенство , k – min число дуг в min пути.

3. Обозначим , последовательно определяем номера , ;

+ ; =

+ ; =

+ ; =

4. min путь из вершины в вершину имеет вид , , … , .

Замечания: 1. С помощью описанного алгоритма можно найти путь min длины в ненагруженном орграфе, для того достаточно всем имеющим дугам одинаковую длину=1.

2. При решении некоторых задач возникает необходимость найти максимальный

путь, эту задачу также можно решить с помощью описанного алгоритма, для этого к каждой

дуге данного нагруженного орграфа поставим в соответствие длину, противоположной

заданной длине.

3. После того, как будет найден путь min длины для орграфа с

противоположными длинами дуг нужно поменять знак у полученной длины пути.

4. Алгоритм Форда-Беллмана применим только к тем нагруженным орграфам, в

которой отсутствует циклы отрицательной длины.