Comments 9
Спасибо за статью — очень наглядно. А есть ли какие-то методы, позволяющие обсчитать граф с негативным циклом? Ну, к примеру, наложить условие, что по циклу можно проходить только 1 раз… или что-то в этом роде.
Алгоритм Беллмана-Форда позволяет определить наличие отрицательного контура — если при N-ом проходе были изменения, значит, есть цикл с отрицательной суммой. Да, вы можете запретить запретить проходить по одному ребру более одного раза.
На первой стадии алгоритма вместо обычного алгоритма Беллмана-Форда можно использовать его улучшенную версию под названием SPFA: Shortest Path Faster Algorithm.
Хотя в худшем случае (на специально подобранном графе) у него вычислительная сложность такая же, как у обычного Форда-Беллмана, но зато на случайных графах работает во много раз быстрее.
А пишется не сильно сложней: надо добавить очередь (как при поиске в ширину) и ещё булевский массив. В цикле берём очередную вершину из очереди и смотрим на смежные с ней. Если для какой-то из них оценку получается уменьшить, то кидаем вершину в очередь, но только если там её ещё нету (для быстрой проверки наличия в очереди как раз булевский массив и нужен).
Хотя в худшем случае (на специально подобранном графе) у него вычислительная сложность такая же, как у обычного Форда-Беллмана, но зато на случайных графах работает во много раз быстрее.
А пишется не сильно сложней: надо добавить очередь (как при поиске в ширину) и ещё булевский массив. В цикле берём очередную вершину из очереди и смотрим на смежные с ней. Если для какой-то из них оценку получается уменьшить, то кидаем вершину в очередь, но только если там её ещё нету (для быстрой проверки наличия в очереди как раз булевский массив и нужен).
Отличный разбор. Спасибо!
Суть алгоритма в постоянном «релаксировании» длины маршрута. На каждой итерации мы пробуем попасть из X в Y через промежуточную вершину К, и если этот путь короче – запоминаем уменьшенную длину.
Несовсем верно. Суть алгоритма Флойда — это динамическое программирование, в котором на k-ой итерации ищутся все кратчайшие пути используя вершины 1...k в качестве промежуточных. Именно поэтому важен именно такой порядок циклов — средняя вершина должна идти внешним циклом.
А главное, вы можете объяснить какой вообще смысл в этом алгоритме Джонсона? Почему бы просто не запустить алгоритм Форда-Беллмана из начальной вершины A и найти все нужные вам расстояния?
Спасибо за уточнение. Смысл алгоритма в повышении скорости поиска.
Sign up to leave a comment.
Алгоритм Джонсона на орграфе с отрицательными дугами