Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия, Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки
Сложность алгоритма поиска кратчайшего пути на графе
30.06.2013, 19:43
Последний раз редактировалось alien308 30.06.2013, 19:45, всего редактировалось 1 раз.
Какова сложность алгоритма нахождения кратчайшего пути в направленном взвешеном графе с возможными отрицательными весами и без отрицательных циклов? Встречал утверждение, что это NP полная задача. Или я что то напутал? Вроди бы кратчайший путь инвариантен относительно прибавления ко всем весам константы. И таким образом можно избавится от отрицательных весов.
Xaositect
Re: Сложность алгоритма поиска кратчайшего пути на графе