2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




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

 
 
 
 Re: Сложность алгоритма поиска кратчайшего пути на графе
Сообщение30.06.2013, 19:52 
Аватара пользователя
Алгоритм Форда-Беллмана, сложность $|V|\cdot |E|$.

alien308 в сообщении #741894 писал(а):
Вроди бы кратчайший путь инвариантен относительно прибавления ко всем весам константы.
Это неправда.

 
 
 
 Re: Сложность алгоритма поиска кратчайшего пути на графе
Сообщение30.06.2013, 20:10 
Аватара пользователя
Xaositect, спасибо.

 
 
 [ Сообщений: 3 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group