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

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

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

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