Negative cycles in directed graphs

Question

I am watching a lecture on negative cycles at this link

At time 5:00, the instructor describes a case where it is assumed that no cycles exist. Then he says that any path won't contain a cycle, because if a path exists with a cycle, one can show a shorter path with no cycles, and the cycle could have only been non-negative.

Can someone please help me understand this point ? I can't seem to follow it.

Thanks.

Answer 1

2 cases:

1. If the graph has negative cycles: then the shortest path solution is undefined, because you can make a path of infinitely negative weight by reaching the negative cycle and traversing it an infinite number of times.

2. If the graph does not have negative cycles: then every cycle has non-negative weight. Then if any shortest path solution exists, there must exist some shortest path solution that does not contain a cycle. Suppose a shortest path solution S exists with a cycle C. We know that in this case C has non-negative weight. Hence we can remove C from S to get a path of lower or equal weight S'. Keep applying this process to S' until you get an acyclic path P. P has weight no greater than S, so it is a shortest path, and it is acyclic.

Answer 2

The video you linked is a bit noisy, but as I understand, the non-negative sum cycles part is a constrain on the graph.

If you have G (digraph) with two vertices and two edges, the shortest path containing a cycle will be (if the two vertex are a, and b and the path is given by the visited vertices)

a-b-a-b

So you can give a shorter version by

a-b

If you have four vertices for example and there is a cycle between the second end the third vertex, on the path, then you can eliminate it from your path, and it will be shorter then you go on the cycle.

So any path has a shorter form if it containing one or more cylces, by it or their elemination.

More generally you can eliminate a cycle by finding the exit vertex of it which have to be presented at least twice on the path, and you should delete the list of vetices between the first and last occurance, and the first or the last occurance of the exit vertex.