Сложность алгоритма поиска кратчайшего пути на графе

[alien308]

Какова сложность алгоритма нахождения кратчайшего пути в направленном взвешеном графе с возможными отрицательными весами и без отрицательных циклов? Встречал утверждение, что это NP полная задача. Или я что то напутал? Вроди бы кратчайший путь инвариантен относительно прибавления ко всем весам константы. И таким образом можно избавится от отрицательных весов.

[Xaositect]

Алгоритм Форда-Беллмана, сложность $|V|\cdot |E|$.

alien308 в сообщении #741894 писал(а):

Вроди бы кратчайший путь инвариантен относительно прибавления ко всем весам константы.

Это неправда.

[alien308]

Xaositect, спасибо.