No negative cycles when determining path between two nodes

Question

Why can't a directed weighted graph contain cycles of negative weight, if we want to determine the shortest path between two nodes of that graph?

Answer 1

Because a negative cycle would affect the path-weight in the following-way:

a----------b-----------c---------------d
     2     |     2     |       4
           |           |
           | -3        | -3
           |           |
           e-----------f
                 2

First attempt of finding a path:

a->b->c->d cost = 8

Now let's enter the loop:

a->b->c->f->e->b->c->d cost = 8 + (-2)

Well that's cheaper by two, but we can do better:

a->b->c->(f->e->b->c)^i->d cost = 8 + (-2) ^ i

The obvious problem: with every run through the loop the path gets cheaper and we wind up with an endless loop as shortest path.

But this doesn't apply to all path-finding algorithms. For example the Bellman-Ford-algorithm is capable of handling negative edges, with the cost of being less efficient.

Answer 2

Because if there such a cycle, for every "shortest path" that you may think, I can pick a better one by simply traversing this negative cycle once again. And this will definitely decrease the overall path cost, because by assumption this cycle is of negative weight.

Answer 3

Because "shortest" actually means "least cost/weight" path.

By having a cycle of negative weight it's possible to use it to get the weight of a ny path (containing this cycle) arbitrary low.

Answer 4

Because if it does, the shortest path can be -inf.

Imagine this example, you want to compute the shortest path between A and D. Probably you want it to be A - B - D, 6 steps. But you can loop the cycle B - C - B as many times as you want. Then, the shortest path is A - B - C - B - C - ... - B - C - B - D.