Студопедия

Главная страница Случайная страница

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






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




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

■ Решают задачу для единственного источника за линейное время.

■ Решают задачу для всех пар за время, пропорциональное VE.

■ Решают другие задачи, например, поиск наиболее длинных путей.



Часть 5. Алгоритмы на графах


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

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

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

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

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

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

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

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



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

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

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

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



mylektsii.ru - Мои Лекции - 2015-2018 год. (0.006 сек.)Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав Пожаловаться на материал