let be a permutation. let , and let be the smallest positive integer so that (which we know exists by lem-perm-1). then we say that the entries form an -cycle in .
a negative cycle in a graph is a cycle whose edges are such that the sum of their weights is a negative value.
negative cycles prevent some challenges when dealing with weighted graphs, as they can form cycles with a weight of .
consider the following graph whose weights function is taken from the real number line
at first glance the distance from to seems to equal 10, but if we were to go back and forth from the node to we'd find that on each step the distance decreases by -2, which would mean that the distance equals , this is why when dealing with negative weights we only consider directed graphs