Кратчайшие пути в ациклических сетях

В первых двух случаях мы устраняем из времени выполнения логарифмический мно­житель, который присутствует в наших лучших алгоритмах для разреженных сетей; в тре­тьем случае мы получаем простые алгоритмы решения задач, которые трудноразрешимы для сетей общего вида. Все эти алгоритмы являются прямыми расширениями алгоритмов для достижимости и транзитивного замыкания на DAG, которые рассматривались в гла­ве 19.

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

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

Вот четыре базовых концепции, примененные нами в главе 19 для получения эффек­тивных алгоритмов для невзвешенных DAG, которые оказываются даже более эффектив­ными на взвешенных DAG:

■ Использование DFS при решении задачи с единственным источником.

■ Использование очереди источников при решении задачи с единственным источником.

■ Вызов любого метода один раз для каждой вершины при решении задачи для всех
пар.

■ Использование единственного DFS (с динамическим программированием) при
решении задачи для всех пар.

Эти методы решают задачу с единственным источником за время, пропорциональное Е, и задачу для всех пар — за время, пропорциональное VE. Все они эффективны ввиду топологического упорядочения, которое позволяет вычислять кратчайшие пути для каж­дой вершины без необходимости повторной проверки предыдущих решений. В этом раз­деле мы рассматриваем по одной реализации для каждой задачи; остальные мы оставля­ем читателям на самостоятельную проработку (см. упражнения 21.62-21.65).

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

Кратчайшие пути из нескольких источников. При заданном наборе начальных вершин, для каждой из остальных вершин w найти кратчайший путь среди всех кратчайших пу­тей из каждой начальной вершины в w.

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