Алгоритм Флойда-Варшалла, работающий с отрицательными циклами

Question

Как можно изменить алгоритм Флойда-Варшалла, чтобы найти кратчайший путь любого цикла отрицательной стоимости ориентированного графа, который поддерживает O(V^3) временную сложность?

Answer 1

В графе с отрицательным циклом нет кратчайшего пути для каждого пути - можно найти более короткий путь, пройдя цикл еще раз.

Если вы имеете в виду кратчайший простой путь (каждую вершину можно посетить не более одного раза) - это невозможно сделать, если только P = NP, и, скорее всего, нет.

Предположим, у вас есть эффективный алгоритм кратчайшего простого пути A,
Приведен пример задачи о длинном пути и график G=(V,E,w)создать новый график G'=(V,E,w') где w'(u,v) = -1*w(u,v), Теперь вызовите A на G'и вы получили кратчайший простой путь на G' - какой самый длинный путь на G,

Однако, поскольку Longest Path является NP-Hard - такое решение невозможно, если P=NP.

---

ТЛ; др:

• В графе с отрицательным циклом нет такого понятия, как кратчайший путь.
• Вы не можете найти кратчайший простой путь в графе с отрицательными циклами в O(V^3) время (если P=NP, и даже тогда это не обязательно будет O(V^3)).