Поиск кратчайших путей в планарных графах с отрицательными весами ребер

Ключевые слова и синонимы

Поиск кратчайших путей в планарных графах с весами дуг общего вида; поиск кратчайших путей в планарных графах с произвольными весами дуг

Постановка задачи

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

На графах общего вида лучший известный алгоритм – алгоритм Беллмана-Форда – выполняется за время O(mn), где n и m – число вершин и ребер, соответственно. Алгоритмы на графах, не имеющих ребер с отрицательными весами, выполняются намного быстрее. К примеру, алгоритм Дейкстры в реализации с фибоначчиевой кучей требует O(m + n log n) времени, а в случае с целочисленными весами алгоритм Торупа выполняется за линейное время. Голдберг [5] также представил алгоритм с временем выполнения [math]\displaystyle{ O(m \sqrt{n} \; log \; L) }[/math], где L – абсолютная величина наибольших отрицательных весов ребер. Заметим, что его алгоритм является слабо полиномиальным.

Нотация

Пусть даны ориентированный граф G = (V, E) и весовая функция [math]\displaystyle{ w: E \to \mathbb{R} \; }[/math] на его ориентированных ребрах. Маркировка расстояния для вершины-источника s представляет собой функцию [math]\displaystyle{ d: V \to \mathbb{R} \; }[/math], такую, что d(v) имеет минимальную длину среди всех путей из s в v, где длина пути P определена как [math]\displaystyle{ \sum_{e \in P} w(e) \; }[/math].

Задача 1 (Поиск кратчайших путей с единственным источником)

Дано: ориентированный граф G = (V, E), весовая функция [math]\displaystyle{ w: E \to \mathbb{R} \; }[/math], вершина-источник [math]\displaystyle{ s \in V \; }[/math].

Требуется: если граф G не содержит циклов отрицательной длины, вывести маркировку расстояния d для вершины-источника s. В противном случае выдать сообщение, что в графе имеется цикл отрицательной длины.

Алгоритм Факчаренфола и Рао [4] предназначен для случая планарных графов и выполняется за время [math]\displaystyle{ O(n \; log^3 \; n) }[/math], улучшив время [math]\displaystyle{ O(n^{3/2}) \; }[/math] алгоритма Липтона, Роуза и Тарьяна [9] и [math]\displaystyle{ O(n^{4/3} \; log \; nL) }[/math] – алгоритма Хензингера, Клейна, Рао и Субраманиама [6].

Этот алгоритм, как и все предыдущие, использует технику рекурсивной декомпозиции и строит структуру данных под названием «плотный граф расстояний», которая будет описана ниже.

Декомпозиция графа представляет собой множество подмножеств [math]\displaystyle{ P_1, P_2, ..., P_k \; }[/math] (не обязательно непересекающихся), таких, что объединение всех подмножеств равно V и для всех ребер [math]\displaystyle{ e = (u, v) \in E \; }[/math] существует уникальное множество [math]\displaystyle{ P_i \; }[/math], содержащее e. Вершина v является граничной вершиной множества [math]\displaystyle{ P_i \; }[/math], если [math]\displaystyle{ v \in P_i \; }[/math] и существует ребро e = (v, x), такое, что [math]\displaystyle{ x \notin P_i \; }[/math]. Подграф, порожденный на подмножестве [math]\displaystyle{ P_i \; }[/math], называется фрагментом декомпозиции.

Алгоритм выполняет рекурсивную декомпозицию: на каждом уровне фрагмент с n вершинами и r граничными вершинами разделяется на два подфрагмента, таких, что каждый подфрагмент содержит не более [math]\displaystyle{ 2n/3 \; }[/math] вершин и не более [math]\displaystyle{ 2r/3 + c \sqrt{n} \; }[/math] граничных вершин при некотором константном значении c. В данном рекурсивном контексте граничной вершиной подфрагмента считается любая граничная вершина исходного фрагмента и любая новая граничная вершина, порожденная декомпозицией фрагмента.

Уровень декомпозиции в рамках этого процесса может быть определен естественным образом. Исходный граф в целостном виде имеет 0 уровень декомпозиции, фрагменты первой декомпозиции исходного графа – 1 уровень, и так далее.

Для каждого фрагмента декомпозиции рекурсивно вычисляются расстояния по кратчайшим путям между всеми его граничными вершинами, лежащим строго внутри фрагмента. Эти расстояния формируют множество ребер непланарного графа, представляющего кратчайшие пути между граничными вершинами. Плотный граф расстояний планарного графа представляет собой объединение этих графов по всем уровням.

При помощи плотного графа расстояний можно получить ответы на запросы о кратчайшем расстоянии между парами вершин.

Задача 2 (Структура данных для поиска кратчайших путей)

Дано: ориентированный граф G = (V, E), весовая функция [math]\displaystyle{ w: E \to \mathbb{R} \; }[/math], вершина-источник [math]\displaystyle{ s \in V \; }[/math].

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

Алгоритм Факчаренфола и Рао в значительной мере опирается на планарность графа; он использует свойства, относящиеся к тому, как пересекаются кратчайшие пути в каждом фрагменте. Таким образом, в отличие от предыдущих алгоритмов, которым требовалась только возможность рекурсивной декомпозиции графа с малым количеством граничных вершин [10], этот алгоритм также требует для каждого фрагмента наличия правильного вложения.

Пусть дано вложение фрагмента. Дыра представляет собой ограниченную грань, в которой все смежные вершины являются граничными вершинами. В идеале можно надеяться на то, что существует планарное вложение любого фрагмента рекурсивной декомпозиции, в котором все граничные вершины располагаются на одной грани и упорядочены по кругу, т.е. в каждом фрагменте не имеется дыр. Это не всегда оказывается верным, но алгоритм работает с любой декомпозицией с константным количеством дыр в каждом фрагменте. Эту декомпозицию можно найти за время O(n log n) при помощи алгоритма Миллера [12] для поиска простого циклического сепаратора.

Основные результаты

Теорема 1. Пусть дана рекурсивная декомпозиция планарного графа, такая, что каждый фрагмент декомпозиции содержит не более константного количества дыр. Тогда существует алгоритм, способный построить плотный граф расстояний за время [math]\displaystyle{ O(n \; log^3 \; n) }[/math].

Пусть дана процедура построения плотного графа расстояний. Тогда кратчайшие пути из источника s можно вычислить следующим образом: вначале добавить s в качестве граничной вершины к каждому фрагменту декомпозиции, вычислить плотный граф расстояний и затем расширить расстояния на все внутренние вершины каждого фрагмента. Это может быть выполнено за время [math]\displaystyle{ O(n \; log^3 \; n) }[/math].

Теорема 2. Задача нахождения кратчайших путей с единственным источником для планарного графа с n вершинами, имеющего ребра отрицательного веса, может быть решена за время [math]\displaystyle{ O(n \; log^3 \; n) }[/math].

Плотный граф расстояний можно использовать для получения ответов на запросы о расстоянии между парами вершин.

Теорема 3. При наличии плотного графа расстояний можно вычислить кратчайшее расстояние между любой парой вершин за время [math]\displaystyle{ O(\sqrt{n} \; log^2 \; n) }[/math].

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

Теорема 4. Для планарных графов, имеющих только ребра с неотрицательными весами, существует динамическая структура данных, поддерживающая ответы на запросы о расстояниях и операции обновления, меняющие веса ребер, за амортизированное время [math]\displaystyle{ O(n^{2/3} \; log^{7/3} \; n) }[/math] на одну операцию. Для планарных графов, имеющих ребра с отрицательными весами, существует динамическая структура данных, поддерживающая тот же набор операций с амортизированным временем [math]\displaystyle{ O(n^{4/5} \; log^{13/5} \; n) }[/math] на одну операцию.

Отметим, что динамическая структура данных не поддерживает операции вставки и удаления, поскольку они могут разрушить рекурсивную декомпозицию.

Применение

Задача поиска кратчайших путей давно стала предметом изучения, она находит применение в самых разных областях. Существует множество задач, сводимых к задаче поиска кратчайших путей, в которых предполагаются отрицательные веса ребер; в качестве примера можно привести поиск ориентированной схемы с минимальной средней длиной. Для планарных графов данная задача широко применяется даже в случаях, когда лежащий в основе задачи граф представляет собой решетку. Например, недавно разработанные подходы к сегментации изображений используют функцию определения отрицательных циклов [2, 3]. В числе других областей применения планарных графов можно упомянуть алгоритмы поиска сепараторов [13] и алгоритмы потока с несколькими источниками и несколькими стоками [13].

Открытые вопросы

Клейн [8] предложил технику, улучшающую время построения плотного графа расстояний до [math]\displaystyle{ O(n \; log^2 \; n) }[/math] для случая неотрицательных весов ребер; она также снижает амортизированное время выполнения для динамического случая до [math]\displaystyle{ O(n^{2/3} \; log^{5/3} \; n) }[/math]. Также для планарных графов с неотрицательными весами ребер Кабелло [1] приводит более быстрый алгоритм вычисления кратчайших расстояний между k парами вершин. Однако задача улучшения границы [math]\displaystyle{ O(n \; log^3 \; n) }[/math] алгоритма нахождения кратчайших путей в планарных графах с весами ребер общего вида все еще остается нерешенной.

Неизвестно, как обрабатывать вставку и удаление ребер в динамической структуре данных. Возможно, потребуется введение новой структуры данных вместо плотного графа расстояний, поскольку последний определяется посредством декомпозиции.

См. также

Литература

1. Cabello, S.: Many distances in planar graphs. In: SODA '06: Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, pp. 1213-1220. ACM Press, New York (2006)

2. Cox, I.J., Rao, S. B., Zhong, Y.: 'Ratio Regions': A Technique for Image Segmentation. In: Proceedings International Conference on Pattern Recognition, IEEE, pp. 557-564, August (1996)

3. Geiger, L.C.D., Gupta, A., Vlontzos, J.: Dynamic programming for detecting, tracking and matching elastic contours. IEEE Trans. On Pattern Analysis and Machine Intelligence (1995)

4. Fakcharoenphol, J., Rao, S.: Planar graphs, negative weight edges, shortest paths, and near linear time. J. Comput. Syst. Sci. 72,868-889(2006)

5. Goldberg, A.V.: Scaling algorithms for the shortest path problem. SI AM J. Comput. 21,140-150 (1992)

6. Henzinger, M.R., Klein, P.N., Rao, S., Subramanian, S.: Faster Shortest-Path Algorithms for Planar Graphs. J. Comput. Syst. Sci. 55,3-23 (1997)

7. Johnson, D.: Efficient algorithms for shortest paths in sparse networks. J. Assoc. Comput. Mach. 24,1-13 (1977)

8. Klein, P.N.: Multiple-source shortest paths in planar graphs. In: Proceedings, 16th ACM-SIAM Symposium on Discrete Algorithms, pp. 146-155 (2005)

9. Lipton, R., Rose, D., Tarjan, R.E.: Generalized nested dissection. SIAM. J. Numer. Anal. 16,346-358 (1979) 10. Lipton, R.J., Tarjan, R.E.: A separator theorem for planar graphs. SIAM. J. Appl. Math. 36, 177-189 (1979) 11. Miller, G., Naor, J.: Flow in planar graphs with multiple sources and sinks. SIAM J.Comput. 24,1002-1017(1995) 12. Miller, G.L.: Finding small simple cycle separators for 2-connected planar graphs. J. Comput. Syst. Sci. 32,265-279 (1986) 13. Rao, S.B.: Faster algorithms for finding small edge cuts in planar graphs (extended abstract). In: Proceedings of the Twenty-Fourth Annual ACM Symposium on the Theory of Computing, pp. 229-240, May (1992) 14. Thorup, M.: Compact oracles for reachability and approximate distances in planar digraphs. J. ACM 51,993-1024 (2004)