Как получить кратчайший путь из одного источника для графиков с отрицательным циклом веса

Question

Эй, я изучал алгоритм Беллмана Форда для задач "кратчайший путь из одного источника".

Теперь я застрял в одном месте, где мне нужно найти решение для графика, имеющего отрицательный весовой цикл.

Но алгоритм Беллмана Форда здесь не работает.

Может кто-нибудь подсказать мне, что делать. Как решить проблему с отрицательным циклом веса?

Спасибо за ваше время.

Answer 1

Если существует отрицательный цикл, который доступен от источника, который Беллман-Форд может обнаружить, то у вас есть два варианта: либо разрешить повторяющиеся ребра, либо нет. Если вы разрешите повторять ребра, ваш кратчайший путь можно считать бесконечно отрицательным. В противном случае, если нет, проблема в том, что NP завершен. Из Википедии:

Один NP-полный вариант задачи о кратчайшем пути запрашивает кратчайший путь в G (содержащий отрицательный цикл), чтобы ребро не повторялось.

Answer 2

В статье, обсуждаемой здесь, авторы (Вульф-Нильсон, Нанонгки, Берштейн) упоминают, что граф с циклами отрицательного веса может быть сведен к графу без таких циклов, а затем они предлагают метод, который находит кратчайший путь почти за линейное время.