Алгоритм Джонсона на орграфе с отрицательными дугами

[iNikNik]

Спасибо за статью — очень наглядно. А есть ли какие-то методы, позволяющие обсчитать граф с негативным циклом? Ну, к примеру, наложить условие, что по циклу можно проходить только 1 раз… или что-то в этом роде.

[FFormula]

Алгоритм Беллмана-Форда позволяет определить наличие отрицательного контура — если при N-ом проходе были изменения, значит, есть цикл с отрицательной суммой. Да, вы можете запретить запретить проходить по одному ребру более одного раза.

[iNikNik]

Спасибо. У меня была примерно такая же идея, но чтобы не писать свою реализацию — после нахождения контура я его заменял отдельной вершиной с весом равным одному проходу по контуру.

Но не покидала мысль, что может быть ученые умы как-то более элегантно решают это задачу)

[igand]

На первой стадии алгоритма вместо обычного алгоритма Беллмана-Форда можно использовать его улучшенную версию под названием SPFA: Shortest Path Faster Algorithm.
Хотя в худшем случае (на специально подобранном графе) у него вычислительная сложность такая же, как у обычного Форда-Беллмана, но зато на случайных графах работает во много раз быстрее.
А пишется не сильно сложней: надо добавить очередь (как при поиске в ширину) и ещё булевский массив. В цикле берём очередную вершину из очереди и смотрим на смежные с ней. Если для какой-то из них оценку получается уменьшить, то кидаем вершину в очередь, но только если там её ещё нету (для быстрой проверки наличия в очереди как раз булевский массив и нужен).

[FFormula]

Да, это логичная и хорошая оптимизация алгоритма — хранить список вершин, которые изменились и которые могут повлиять на очередные релаксации в графе. Спасибо за комментарий!

[0serg]

Отличный разбор. Спасибо!

[wataru]

Суть алгоритма в постоянном «релаксировании» длины маршрута. На каждой итерации мы пробуем попасть из X в Y через промежуточную вершину К, и если этот путь короче – запоминаем уменьшенную длину.

Несовсем верно. Суть алгоритма Флойда — это динамическое программирование, в котором на k-ой итерации ищутся все кратчайшие пути используя вершины 1...k в качестве промежуточных. Именно поэтому важен именно такой порядок циклов — средняя вершина должна идти внешним циклом.

А главное, вы можете объяснить какой вообще смысл в этом алгоритме Джонсона? Почему бы просто не запустить алгоритм Форда-Беллмана из начальной вершины A и найти все нужные вам расстояния?

[FFormula]

Спасибо за уточнение. Смысл алгоритма в повышении скорости поиска.

[wataru]

Смысл алгоритма в повышении скорости поиска.

В смысле, повышения скорости поиска? Он же медленнее! Вместо одного форда беллмана этот алгоритм делает сначала вспомогательного форда беллмана (да еще и в расширенном на одну вершину графе), а потом еще и дейкстру.