![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Кратчайшие пути в ациклических сетях
В главе 19 мы обнаружили, что вопреки нашим предположениям о том, что DAG должны быть проще в обработке, чем обычные орграфы. Разработка алгоритмов с существенно большей производительностью для DAG, нежели для обычного ориентированного графа, является труднодостижимой целью. Для задач о кратчайших путях мы действительно имеем алгоритмы для DAG, которые проще и быстрее, чем методы, основанные на очереди с приоритетами, которые рассматривались для обычных орграфов. В частности, в этом разделе мы исследуем алгоритмы для ациклических сетей, которые: ■ Решают задачу для единственного источника за линейное время. ■ Решают задачу для всех пар за время, пропорциональное VE. ■ Решают другие задачи, например, поиск наиболее длинных путей. Часть 5. Алгоритмы на графах
Поскольку нет циклов вообще, то нет и отрицательных циклов, так что отрицательные веса не вызывают трудностей в задачах поиска кратчайших путей на DAG. Соответственно, в пределах этого раздела мы не накладываем ограничений на значения весов ребер. Есть одно замечание, касающееся терминологии: у нас есть выбор, как называть ориентированные графы с весами на ребрах и без циклов —• либо взвешенными DAG, либо ациклическими сетями. Мы применяем оба термина как для того, чтобы попеременно делать ударение на их эквивалентности, так и для того, чтобы избежать путаницы, когда мы обращаемся к литературе, где широко используются оба термина. Иногда удобно использовать первый из них, чтобы сделать акцент на отличии от невзвешенного DAG, когда имеется в виду взвешенность, и второй - чтобы сделать акцент на отличиях от обычных сетей, которые подразумеваются ациклическими. Вот четыре базовых концепции, примененные нами в главе 19 для получения эффективных алгоритмов для невзвешенных DAG, которые оказываются даже более эффективными на взвешенных DAG: ■ Использование DFS при решении задачи с единственным источником. ■ Использование очереди источников при решении задачи с единственным источником. ■ Вызов любого метода один раз для каждой вершины при решении задачи для всех ■ Использование единственного DFS (с динамическим программированием) при Эти методы решают задачу с единственным источником за время, пропорциональное Е, и задачу для всех пар — за время, пропорциональное VE. Все они эффективны ввиду топологического упорядочения, которое позволяет вычислять кратчайшие пути для каждой вершины без необходимости повторной проверки предыдущих решений. В этом разделе мы рассматриваем по одной реализации для каждой задачи; остальные мы оставляем читателям на самостоятельную проработку (см. упражнения 21.62-21.65). Начнем с небольшого ухищрения. Каждый DAG имеет, по крайней мере, один источник, но мог бы иметь несколько, так что вполне естественно обсудить следующую задачу о кратчайших путях. Кратчайшие пути из нескольких источников. При заданном наборе начальных вершин, для каждой из остальных вершин w найти кратчайший путь среди всех кратчайших путей из каждой начальной вершины в w. Эта задача по существу эквивалентна задаче о кратчайших путях для единственного источника. Мы можем свести задачу для нескольких источников к задаче для единственного источника, добавив фиктивную вершину-источник с ребрами нулевой длины к каждому источнику в сети. И наоборот, мы можем свести задачу для единственного источника к задаче для нескольких источников, работая с искусственной подсетью,
|