64 4. Пути в сетях
В случае задания бесконтурной сети списками
←−
list расстояния от
v
1
до всех остальных вершин также могут быть вычислены за время
O(m). Такой алгоритм получается легкой модификацией алгоритма 4.4.
Предоставляем читателям возможность самостоятельно подправить ал-
горитм 4.4 для достижения указанной цели.
В заключение от метим, что все три основных алгоритма (Форда-
Беллмана, Дейкстры и алгоритм 4.4) вычисления расстояний от фикси-
рованной вершины легко могут быть модифицированы для вычисления
расстояний от фиксированной вершины в сетях со взвешенными верши-
нами.
4.5. Задача о максимальном пути и сетевые графики
Задача о максимальном пути формулируется следующим образом:
в заданной сети G = (V, E, c) с выделенной вершиной s для каждой
вершины v ∈ V найти (s, v)- путь, имеющий максимальную длину среди
всех возможных (s, v)-путей в сети G.
Отметим, что имеет смысл решать эту задачу лишь в сетях, не содер-
жащих контуров положительной длины. Рассмотрев тогда сеть, отлича-
ющуюся от исходной только изменением знаков весов дуг, получим сеть,
в которой нет контуров отрицательной длины. Применяя к новой сети
алгоритм Форда-Беллмана, можно построить кратчайшие (s, v)-пути,
которые будут путями максимальной длины в исходной сети.
Впрочем, задачу о максимальном пути в общем случае можно ре-
шать и непосредственно, заменяя в алгоритме Форда-Беллмана знак
неравенства в строке 9 на противоположный.
Разумеется, решая таким образом задачу о максимальном пу ти, вес
несуществующих дуг следует положить равным −∞.
Важный частный случай сети с неотрицательными весами дуг, не
имеющей контуров положительной длины, — это сеть с неотрицатель-
ными весами дуг, в которой вообще нет контуров. В этом частном случае
задача о максимальном пути может быть решена алгоритмом 4.4, в ко-
тором +∞ заменяется на −∞, а знак неравенства в строке 6 меняется
на противоположный. Несложное доказательство ко рректности исправ-
ленного таким образом алгоритма 4.4 мы предоставляем читателю.
Отметим, что подобная замена знака неравенства в алгоритме Дейкс-
тры не позволяет получить алгоритм решения задачи о максимальном
пути. Для примера достаточно рассмотреть сеть, изображенную на рис.
16. Здесь такая модификация алгоритма Дейкстры, неправильно опре-