Отрицательные циклы во взвешенных орграфах: различия между версиями

Пусть G = (V, E) – ориентированный граф (орграф), имеющий m ребер и n вершин, ребра которого ассоциированы с вещественной стоимостной функцией wt: E ! R. Стоимость, wt(P), пути P в графе G равна сумме стоимостей ребер, входящих в P. Простой путь C, начальная и конечная вершины которого совпадают, называется циклом. Если wt(C) < 0, то C называется отрицательным циклом. Необходимо определить, существует ли подобный цикл в данном орграфе G с ребрами вещественной стоимости, и если существует – вывести этот цикл.

Задача нахождения отрицательного цикла тесно связана с задачей нахождения кратчайшего пути. В последней необходимо найти путь с минимальной стоимостью между двумя вершинами s и t. Легко увидеть, что кратчайший путь s-t существует в том и только том случае, если ни один путь s-t в графе G не содержит отрицательного цикла [1 , 13]. Также известно, что все кратчайшие пути от заданной вершины s до всех других вершин формируют дерево, называемое деревом кратчайших путей [1, 13].