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

Теорема 1. Пусть дана рекурсивная декомпозиция планарного графа, такая, что каждый фрагмент декомпозиции содержит не более константного количества дыр. Тогда существует алгоритм, способный построить плотный граф расстояний за время O(n log n).

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

Теорема 2. Задача нахождения кратчайших путей с единственным источником для планарного графа с n вершинами, имеющего ребра отрицательного веса, может быть решена за время O(n log3 n).

Теорема 3. При наличии плотного графа расстояний можно вычислить кратчайшее расстояние между любой парой вершин за время O(pn log2 n).

Теорема 4. Для планарных графов, имеющих только ребра с неотрицательными весами, существует динамическая структура данных, поддерживающая ответы на запросы о расстояниях и операции обновления, меняющие веса ребер, за амортизированное время O(n2/3 log n) на одну операцию. Для планарных графов, имеющих ребра с отрицательными весами, существует динамическая структура данных, поддерживающая тот же набор операций с амортизированным временем O(n4/5 log n) на одну операцию.