Кратчайший цикл в ориентированном графе
Материал из Algocode wiki
Версия от 13:35, 26 сентября 2019; Глеб (обсуждение | вклад) (Новая страница: «Попытаемся из каждой вершины найти кратчайший цикл, проходящий через неё, с помощью BFS. Э...»)
Попытаемся из каждой вершины найти кратчайший цикл, проходящий через неё, с помощью BFS. Это делается аналогично обычному BFS: мы должны найти расстояний от вершины до самой себя, при этом не считая, что оно равно $0$.
Итого, у нас $|V|$ запусков BFS, и каждый запуск работает за $O(|V| + |E|)$. Тогда общее время работы составляет $O(|V|^2 + |V| |E|)$. Если инициализировать массив $dist$ единожды, а после каждого запуска BFS возвращать исходные значения только для достижимых вершин, решение будет работать за $O(|V||E|)$.
Автор конспекта: Глеб Лобанов
По всем вопросам пишите в telegram @glebodin