Предположим, у нас есть орграф, содержащий ребра как с положительным, так и с отрицательным весом.
Я понимаю, что решение кратчайшего пути — это алгоритм Беллмана-Форда.
Мой вопрос: почему мы не можем просто добавить какое-то большое значение N ко всем затратам ребер, чтобы больше не было отрицательных ребер, а затем использовать гораздо более эффективный алгоритм Дейкстры?
