Модифицированный метод Форда

Этот метод предназначен для нахождения критического пути на сетевом графе (сети). Сеть представляет собой связный бесконтурный орграф G = (X, U) с произвольными весами дуг l (x_i, x_j), имеющий только одну входную вершину (источник) s Î X, удовлетворяющую условию Г^-1(s) = Ø, и одну выходную вершину сток t Î X, для которой Г(t) = Ø.

Сущность метода заключается в одновременном определении для каждой вершины x_i графа максимального расстояния l(x_i) от источника s и максимального расстояния g(x_i) до стока t. Сумма значений l^*(x_i) и g^*(x_i) показывает длину максимального пути от s до t, который проходит через вершину x_i. Отсюда длина критического пути m[ s, t ] в сети определяется как

Важной особенностью модифицированного метода Форда является отсутствие требования правильной нумерации вершин графа, так как на каждой итерации просматриваются не вершины, а дуги сети. Формальная схема алгоритма приводится ниже.

Алгоритм 2.2 (поиск критического пути

модифицированным методом Форда)

Данные: сеть G = (X, U) c n вершинами и m дугами, где s - входная и
t - выходная вершины сети.

Результаты: длины l^*(x_i) и g^*(x_i) максимальных путей m[ s, x_i ] и m[ x_i, t ], где i = , соответственно.

Шаг 1 (присвоение начальных значений)

Определить начальные значения l⁽⁰⁾(x_i) = 0, g⁽⁰⁾(x_i) = 0 для всех вершин x_i Î X. Установить номер итерации k = 1.

Шаг 2 (итерационный процесс)

Для всех дуг сети вычислить новые значения пометок вершин x_i и x_j:

(2.2)

где l¢(x_i) и g¢(x_j) - предыдущие значения пометок.

Шаг 3 (проверка условий окончания)

а) Если k = n, то переход к шагу 4.

б) Если k < n и для всех выполняются условия:

,

то переход к шагу 4. Иначе присвоить k = k + 1 и переход к шагу 2.

Шаг 4 (получение результатов)

Присвоить l^*(x_i) = l^(k)(x_i) и g^*(x_i) = g^(k)(x_i) для всех x_i Î X. Конец алгоритма.

За один просмотр дуг сети на шаге 2 значения l(x_i) и g(x_i) для одной и той же вершины могут изменяться многократно (в случае │Г^-1(x_i)│ > 1 или │Г(x_i)│ > 1). Если в результате выполнения очередной итерации хотя бы одна пометка любой вершины принимает новое значение, то процесс повторяется. В предельном случае число итераций может достигать значения n. Поэтому вычислительная сложность алгоритма 2.2 оценивается как O (nm) операций.

Модифицированный метод Форда является наиболее универсальной процедурой, так как его результаты определяют длину критического пути m[ s, t ], а также одновременно длины максимальных путей m[ s, x_i ] и m[ x_i, t ] для каждой вершины x_i сети. Построение любого из указанных путей производится с использованием соотношения (1.2).

Пример 2.1. Применение алгоритма 2.2 демонстрируется для сети G = (X, U), заданной в виде списка дуг и показанной на рис. 2.1.

Результаты работы алгоритма 2.2 представлены в табл. 2.1, где используются следующие обозначения: l _i = l(x_i); g _i = g _i (x_i). На первой и второй итерациях пометки вершин несколько раз принимают новые значения, поэтому таблица содержит соответствующее число столбцов. На третьей итерации пометки не изменяются, а длина критического пути определяется как l^*(x ₇) = g^*(x ₁) = 26.

Рис.2.1. Сеть и ее список дуг для примера 2.1

Таблица 2.1

Результаты применения алгоритма 2.2 для примера 2.1

В заключение следует отметить, что модифицированный метод Форда можно использовать для решения задачи поиска кратчайших путей. Для этого в формулах (2.2) операцию max следует заменить на min.

У П Р А Ж Н Е Н И Я

2.11. Модифицированным методом Форда найти критический путь в графе, представленном на рис. 1.7.

2.12. Составить программу поиска экстремальных путей по алгоритму 2.2.

2.13. Решить задачу из упражнения 1.39 модифицированным методом Форда и сравнить полученные результаты.

2.14. Для графа на рис.1.8 определить пути максимальной длины от x ₁ до всех других вершин.