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

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

алгоритм зависит от нахождения новой весовой функции (w '), которая является положительной для всех ребер и сохраняет правильность соотношений кратчайших путей.

Это достигается путем вычисления значений h (s), h (d), которые будут добавлены к исходному значению w.

Мой вопрос: почему бы просто не найти наименьшее w в графе и добавить его ко всем ребрам? это удовлетворит оба условия и потребует меньшего количества вычислений.

algorithms graph-theory graphs shortest-path Mr.Me
источник

Вы пытались доказать свою претензию или нашли контрпример? Подсказка: ваша интуиция не так. (Сообщество, я уверен, что это дубликат. Можете ли вы найти его?)

Рафаэль

@ Рафаэль Я уверен, что это тоже обман, но я подумал, что будет быстрее ответить на него, чем найти обман.

Дэвид Ричерби

@ Рафаэль Мне очень жаль, так как я не смог сформулировать свой вопрос в определенном формате, я не смог его найти.

Mr.Me

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

Ответы:

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

Например, предположим, что у ребра с наименьшей стоимостью есть вес $-2$ и есть два пути от $a$ до $b$ : один ребро веса $3$ и путь с двумя ребрами, каждый из которых имеет вес $1$ . Двухгранная дорожка имеет наименьший вес. Однако, если вы добавите $2$ к каждому ребру, путь с одним ребром имеет вес $5$ а путь с двумя ребрами теперь имеет вес $6$ , поэтому вы получите неправильный ответ.

Дэвид Ричерби
источник

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

Pendechosen
источник

Этот эффект уже упоминался в другом ответе.

Юваль

Я просто перефразировал это до степени замешательства.

Pendechosen