Я не знаю, баяном ли является то, что я придумал, но единственный алгоритм, который я нашел на емаксе, решает задачу при помощи Флойда-Уоршелла, который, как известно, работает за O(n3). Ниже приводится описание алгоритма, который работает за O(n*m).
Итак, суть задачи. У нас есть произвольный ориентированный граф с n вершинами и m ребрами, нужно найти все пары вершин, такие что путь между ними бесконечно мал.
Шаг 1. Из данного графа получим конденсацию.
Следующее утверждение: если в компоненте сильной связности есть цикл отрицательного веса, то между любой парой вершин из этой компоненты сильной связности есть бесконечно малый путь.
В самом деле, доберемся из начальной вершины до цикла - а это мы можем сделать, так как у нас компонента сильной связности, - пройдем по циклу любое произвольное число раз и перейдем в нашу вторую вершину - опять же, мы сможем это сделать в силу КСС.
Шаг 2. Итак, запустим Форда-Беллмана в каждой КСС. Он найдет нам отрицательный цикл, если он есть.
Шаг 3, а. Произведем серию поисков в ширину на 0-1 графе из каждой вершины полученной конденсации.
Давайте будем называть "черной" ту вершину конденсации, у которой внутри нее есть цикл отрицательного веса.
Утверждение: если в первоначальном графе между двумя вершинами есть путь, проходящий хотя бы через одну "черную" компоненту связности(включая компоненты связности этих двух вершин), то между двумя вершинами существует сколь угодно малый по величине путь.
Действительно, зайдем в эту компоненту связности, дойдем до цикла, проитерируемся по циклу любое произвольное число раз, и потом выйдем из цикла и дойдем до второй вершины.
Теперь как мы будем осуществлять поиск в ширину. Если первая вершина была черная, то перекрасим всех ее сыновей в черный цвет, и так далее. Иначе сначала переберем всех черных сыновей, и от них запустимся как раньше - покрасим всех сыновей черного сына в черный цвет. Очевидно, что все вершины, которые стали черными - между ними и начальной вершиной лежит вершина, в которой есть цикл отрицательного веса.
Шаг 3, б. Результаты обходов сохраним в матрице смежности.
Шаг 4. Для каждой пары вершин за O(1) найдем, в какой КСС они лежат, и по построенной матрице определим, лежит ли между ними цикл отрицательного веса, так же за O(1).
Асимптотическая сложность: по шагам: 1)O(n*logn) 2)O(n*m) 3)O(n1*m1); так как n1<=n и m1<=m, получим O(n*m). 4)O(n2).
То есть суммарно не более чем O(n*m)
Сложность по памяти: 0) начальный граф - O(m + n) 1) для хранения конденсированного графа O(m + n) и для каждой вершины ссылка на номер ее КСС - O(n) 2-3) под матрицу O(n1*n1) = O(n*n) 4) 0.
Итого O(n2 + 2*m + 3 * n)
Вопросы от автора:
1) это баян?
2) Видите ли вы какие-нибудь оптимизации? Особенно это касается оптимизации по памяти.
Реализация алгоритма - http://pastie.org/2774882
Comments (0)
