Часть 5. Алгоритмы на графах. Общая задача поиска кратчайших путей в сетях, в которых веса ребер могут прини­мать отрицательные значения

Общая задача поиска кратчайших путей в сетях, в которых веса ребер могут прини­мать отрицательные значения, является неразрешимой. Задачи поиска кратчайших путей представляют собой хорошую иллюстрацию той черты, которая часто отделяет неразре­шимые задачи от легких, поскольку у нас имеются многочисленные алгоритмы для реше­ния различных вариантов этой задачи, когда мы накладываем ограничения на сети: то ли на присутствие ребер с положительными весами, то ли на ацикличность, или даже когда мы накладываем ограничения на подзадачи, где допускаются отрицательные веса ребер, но нет отрицательных циклов. Некоторые алгоритмы оптимальны или близки к таковым, хотя есть существенный разрыв между наилучшей известной нижней границей и лучшим известным алгоритмом для задачи с одним источником в сетях, которые не содержат от­рицательных циклов, и для задачи всех пар в сетях с неотрицательными весами.

Эти алгоритмы полностью основаны на небольшом количестве абстрактных действий и могут быть приведены в общей постановке. Говоря конкретно, единственными двумя действиями, которые мы выполняем над весами ребер, являются сложение и сравнение: любая постановка, в которой эти действия имеют смысл, может служить платформой для алгоритмов поиска кратчайших путей. Как уже отмечалось ранее, эта точка зрения объе­диняет наши алгоритмы для вычисления транзитивного замыкания орграфа с алгоритма­ми поиска кратчайших путей в сетях. Сложность, привносимая отрицательными весами ребер, соответствует свойству монотонности на этих абстрактных операциях: если есть возможность гарантировать, что сумма двух весов никогда не меньше любого из весов, то можно использовать алгоритмы из разделов 21.2-21.4. Если же подобной гарантии дать нельзя, необходимо использовать алгоритмы из раздела 21.7. Инкапсуляция упомянутых особенностей в АТД не составляет особого труда, к тому же она расширяет применимость данных алгоритмов.

Задачи поиска кратчайших путей выводят нас на перекресток между элементарными алгоритмами обработки графов и задачами, которые мы не можем решить. Они дают на­чало ряду других классов задач аналогичного характера, в том числе задачи о потоках в сетях и линейное программирование. Как и при поиске кратчайших путей, в этих областях имеется четкая грань между легкими и неразрешимыми задачами. Существуют не только многочисленные эффективные алгоритмы, доступные при соответствующих ограничениях, но также остаются широкие возможности поиска лучших алгоритмов, равно как и встре­чаются случаи, когда доводится лицом к лицу сталкиваться с однозначно NP-трудными задачами.

Многие из таких задач были четко сформулированы как задачи из области исследо­вания операций еще до прихода компьютеров и соответствующих им алгоритмов. Исто­рически дисциплина исследования операций фокусировалась на общих математических и алгоритмических моделях, тогда как информатика - на конкретных алгоритмических решениях и базовых абстракциях, которые могут как иметь выход на эффективные реа­лизации, так и составить основу построения общих решений. Поскольку как модели из области исследования операций, так и базовые алгоритмические абстракции из области информатики были ориентированы на разработку компьютерных реализаций, которые могут решить практические задачи большой размерности, в некоторых областях деятель­ности невозможно провести четкую границу между исследованием операций и информа­тикой. Например, в обеих областях исследователи до сих пор ищут эффективные реше­ния задач, подобных проблеме поиска кратчайших путей.