Блог

У меня есть ориентированный граф с отрицательными весами ребер. График модифицируется программой и иногда образует отрицательные циклы. Когда это происходит, алгоритмы кратчайшего пути (Беллман-Форд / Джонсон / Флойд-Варшалл) обнаружат существование такого отрицательного цикла и завершатся сбоем, но никакой другой полезной информации не будет получено.

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

Спасибо,

Пол

Пол, если вы собираетесь добавить ребро (источник, назначение, вес), и вы знаете расстояние от назначения до источника, то вы создаете отрицательный цикл тогда и только тогда, когда новый вес старое расстояние отрицательны.

С другой стороны, если вы только что получили график, алгоритм Беллмана-Форда обнаруживает отрицательные циклы и может отображать один, когда он его находит. Вам просто нужно либо найти реализацию, которая делает это (а не просто сбой), либо написать ее самостоятельно. Это не сложный алгоритм, и в Интернете есть много псевдокода.

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

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