Можем ли мы использовать Dijkstra в этом случае?

Question

Учитывая график, который имеет отрицательные веса, но мы знаем наверняка это не имеет никакого отрицательного цикла:

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

Правильно ли это, если у нас нет отрицательных циклов? Если у нас есть отрицательные циклы, мы не сможем использовать этот алгоритм, так как ему нужно будет пересмотреть узлы Dijkstra, отмеченные как завершенные.

Answer 1

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

Таким образом, вы не можете применять Дийкстра, даже если нет отрицательного кругового цикла.