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

Question

Предположим, у меня есть график, где минимальный вес ребра равен -100.Могу ли я добавить 100 в качестве смещения ко всем ребрам и использовать алгоритм Дейкстры?

Пожалуйста, помогите мне понять, почему такой метод дает неправильное решение.

Answer 1

Добавление 100 к каждому весу ребра дает неправильное решение, поскольку оно штрафует пути, у которых больше ребер, чем путей, у которых меньше ребер.

Например, предположим, что у нас есть график, а кратчайший путь из точки А в точку В имеет 3 ребра и общее расстояние 5. Предположим, что некоторый другой путь из точки А в точку В имеет 2 ребра, но общее расстояние составляет 10 .

Если мы добавим 100 к каждому весу ребра, то первый путь будет стоить 305, а второй путь - 210. Таким образом, второй путь становится короче первого пути.

Таким образом, мы можем сделать вывод, что добавление смещения или смещения к каждому весу ребра не обязательно сохраняет кратчайшие пути.