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