Кратчайший путь в ориентированном графе с циклами отрицательной длины

Question

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

Мне известен алгоритм Беллмана-Форда , но он терпит неудачу при наличии отрицательных циклов.Также ясно, что обход отрицательных циклов навсегда делает проблему нечеткой, поэтому я ограничиваю путь для посещения каждого узла не более одного раза.

Существует ли такой алгоритм?И есть ли готовая реализация, которую я могу использовать?

--- EDIT ---

Как указано ниже, вот фактическое приложение:

УчитываяНа входном изображении, содержащем почерк, я могу оценить вероятности направления обводки для каждого пикселя:

Затем я могу поместить пиксели в график и найти путь пера:

Видите, как пропущено "l"?Если я могу установить соседние веса, чтобы быть отрицательным, оптимальный путь будет проходить через все буквы.Но отрицательные веса создают отрицательные циклы.

Answer 1

Вы правы, что алгоритм Беллмана-Форда в этом случае не работает. Вы можете сослаться на раздел 2 из этого ресурса . В нем обсуждается проблема для неориентированного графа и работает на основе алгоритма Эдмондса идеального соответствия минимального веса. На самом деле, вас может заинтересовать этот вопрос , который очень похож на ваш.

Если график ориентированный, то, как указал @SaiBot, проблема сводится к NP Hard-проблеме, и эффективное решение невозможно.