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

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