Управление краевыми затратами отрицательно взвешенного орграфа для использования алгоритма Дейкстры

Question

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

Я понимаю, что решением с кратчайшим путем является алгоритм Беллмана-Форда.

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

Answer 1

Добавление константы к длине каждого ребра не монотонно для длины пути, даже для путей между одними и теми же двумя узлами (поскольку пути могут отличаться по количеству ребер).Рассмотрим граф с ребрами ab, bc и ac веса -1.Добавление N=2 переключает кратчайший путь с a на c с ab,bc на ac.