Алгоритм Дейкстры с отрицательными весами

Можем ли мы использовать алгоритм Дейкстры с отрицательными весами?

СТОП! Прежде чем вы подумаете «лол, вы можете просто бесконечно прыгать между двумя точками и получить бесконечно дешевый путь», я больше думаю об одном - Пути тропы.

Примером может служить гористая местность с точками на ней. Очевидно, что переход от высокого уровня к низкому не требует энергии, на самом деле он генерирует энергию (таким образом, отрицательный вес пути)! Но возвращение назад просто не сработает, если вы не Чак Норрис.

Я думал об увеличении веса всех точек, пока они не станут неотрицательными, но я не уверен, что это сработает.

11116120]