Вопрос по algorithm – Почему большинство графовых алгоритмов не так легко адаптируются к отрицательным числам?
==============================================================================================================

[Руководство по разработке алгоритма](http://www.algorist.com/) говорит:

Most graph algorithms do not adapt so easily to negative numbers. Indeed, shortest path algorithms have trouble with negative numbers, and certainly do not generate the longest possible path using this technique.

Но почему? Когда мы просто добавляем отрицательный`-` Я думаю, что перед исходным весом большинство графических задач, связанных с весом, можно решать одинаково, верно?

Потому что, когда вы рассматриваете минимальную или максимальную стоимость пути, вы всегда в конечном итоге учитывает сумму всех отдельных шагов.

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

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

Просто в качестве примера: если у вас есть два узла, соединенных между собой двумя ребрами веса`1` а также`-2` Вы можете создать цикл между ними, чтобы определить путь с произвольной низкой стоимостью (даже`-∞`).



Я специально добавлю ответ на проблему кратчайшего пути. Общая проблема с отрицательными ребрами хорошо описана в[Ответ Джека](https://stackoverflow.com/a/10381508/2157640).

Рассмотрим график`G = (V, E)` с краями длины`l(e) ≤ 0` для каждого края`e ∈ E`, Кратчайший путь в`G` такой же, как самый длинный путь в`G'` с`l'(e) = - l(e) ≥ 0 ∀e ∈ E`. [Самая длинная проблема пути](http://en.wikipedia.org/wiki/Longest_path_problem) Известно, что NP-жесткий в общих графах.*Though it can be solved in linear time in DAGs and other classes of graphs.*

Как[CLS ответил](https://stackoverflow.com/a/10381707/2157640)проблема только с отрицательными циклами и[Алгоритм Беллмана-Форда](http://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm) может справиться с некоторыми краями, являющимися отрицательными. Но алгоритм самого длинного пути должен справляться с циклами в графе, и Беллман-Форд не может дать правильный ответ на графах с отрицательными циклами. Поэтому алгоритм Беллмана-Форда можно использовать для вычисления самого длинного пути только в графах без положительных циклов.*Mentioning, because that idea is* [очевидно не редкость](https://www.or-exchange.org/questions/823/why-cant-we-solve-longest-path-problem-by-using-shortest-path-algoritms).



> 
> Indeed, shortest path algorithms have trouble with negative numbers,
> 
> 
> 

Это верно для[Алгоритм Дейкстры](http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm), но не для алгоритмов кратчайшего пути в целом.[Алгоритм Беллмана-Форда](http://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm) может иметь дело с отрицательными весами ребер, если график не содержит отрицательных циклов. Тем не мение:

> 
> Bellman-Ford can detect negative cycles and report their existence,
> but it cannot produce a correct answer if a negative cycle is not
> reachable from the source.
> 
> 
>