Даже если бы был пример;Вы могли бы, вероятно, нормализовать это, чтобы быть все положительным.Любое фактическое представление отрицательного веса относительно некоторых 0. Я предполагаю, что я говорю, что, вероятно, нет применения отрицательных весов, которые не могут быть сделаны с использованием исключительно положительных весов.
РЕДАКТИРОВАТЬПодумав об этом немного больше, я полагаю, у вас могут возникнуть ситуации, когда данный путь имеет отрицательный вес.В данном контексте;предполагая, что отрицательный вес - это плохо, вы бы столкнулись с ситуацией, когда единственный возможный способ достичь цели достижения желаемой конечной точки означал бы, что на вашем графике должна быть хотя бы одна точка, где вы 'ТРЕБУЕТСЯ пойти по отрицательному пути (как, никакая другая опция не доступна для достижения вашей цели) .Но я полагаю, если график не был пройден;как вы узнали бы, что это правда?
РЕДАКТИРОВАТЬ (СНОВА): @ Джим, я думаю, вы правы.Точка дроссельной катушки не очень актуальна.Я полагаю, я был слишком быстр, чтобы предположить, что это было потому, что один вопрос, который возникает у меня в голове при введении отрицательных ребер, - если возможно пройти по графику, не принимая НИКАКОГО отрицательного ребра, то что отрицательные ребра делают там в первомместо?Но, это не очень хорошо, потому что - вне ретроспективного взгляда - как бы вы узнали, можно ли или нет пройти график, не пройдя отрицательный край?
Также стоит отметить, согласно странице Википедии об алгоритме Джикстры :
Алгоритм Дейкстры, задуманный голландским ученым-компьютерщиком Эдсгером Дейкстрой в 1956 г. и опубликованный в 1959 г., является алгоритмом поиска графа, который решает проблему кратчайшего пути из одного источника для графа с неотрицательным ребром стоимости пути, создавая дерево кратчайшего пути.Этот алгоритм часто используется в маршрутизации и в качестве подпрограммы в других алгоритмах графа.
Итак, хотя этот разговор полезен и заставляет задуматься;может быть, заголовок вопроса должен звучать так: «Какой правильный алгоритм использовать для обхода графа с отрицательными ребрами?»Алгоритм Джикстры был предназначен для поиска кратчайшего пути.Но если вы введете положительные и отрицательные веса, то не изменится ли цель от поиска кратчайшего пути к поиску САМОГО положительного - независимо от того, сколько ребер на выбранном пути?И если да, то каково ваше условие выхода?Единственный способ узнать, что вы достигли оптимального решения, - это если вы натолкнулись на путь, включающий все положительные ребра без каких-либо отрицательных ребер - и разве этот сценарий не случится случайно?Так что - если введение ситуации, в которой есть положительные и отрицательные веса, изменяет цель на наиболее положительную (или отрицательную в зависимости от того, как вы хотите ее сформулировать), эта проблема не будет обречена на O (n!) И, следовательно, будет наилучшейрешается алгоритмом принятия решений (например, альфа / бета), который даст наилучший результат с учетом ограничения на общее количество ребер, которые вы можете взять?