Кратчайший цикл в ориентированном графе

Материал из Algocode wiki
Версия от 16:35, 26 сентября 2019; Глеб (обсуждение | вклад) (Новая страница: «Попытаемся из каждой вершины найти кратчайший цикл, проходящий через неё, с помощью BFS. Э...»)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

Попытаемся из каждой вершины найти кратчайший цикл, проходящий через неё, с помощью BFS. Это делается аналогично обычному BFS: мы должны найти расстояний от вершины до самой себя, при этом не считая, что оно равно $0$.

Итого, у нас $|V|$ запусков BFS, и каждый запуск работает за $O(|V| + |E|)$. Тогда общее время работы составляет $O(|V|^2 + |V| |E|)$. Если инициализировать массив $dist$ единожды, а после каждого запуска BFS возвращать исходные значения только для достижимых вершин, решение будет работать за $O(|V||E|)$.



Автор конспекта: Глеб Лобанов

По всем вопросам пишите в telegram @glebodin