Why is there need to consider the shortest path problem for digraphs with negative cycles?

Question

Consider the shortest path problem on a digraph G=(V,A,W) possibly with negative cycles. We only consider simple paths, i.e. paths with no repeating vertices. By constructing a new graph G'(V,A,W') such that G' and G have the same vertices and arcs, but for each arc, its weight in G' is higher than its weight in G by a constant.

Clearly, if P1 and P2 are two paths, and w(P1) < w(P2) in G, then w'(P1) < w'(P2) in G'. This means a shortest path in G is also a shortest path in G'. By choosing the constant large enough, the weights of G' can all be positive. Therefore it suffices to solve the shortest path problem for G'. Why does the shortest path problem seem like such a big deal for graphs with negative cycles?

Moreover, the shortest path problem with negative cycles is actually NP-hard. If I were right and we can reduce the case with negative cycles to the case without negatives cycles, shouldn't the problem be polynomial?

I guess I am missing something, but I am not sure what.

Answer 1

Clearly, if P₁ and P₂ are two paths, and w(P₁) < w(P₂) in G, then w'(P₁) < w'(P₂) in G'. This means a shortest path in G is also a shortest path in G'.

No, since if weight of a path p in G is denoted as w_p, then the weight of that path in G' is w_p+n_p×c with n_p the number of edges in the path, and c the constant with which you increased each edge.

This means that another path may now be more favorable. That path might have more expensive edges in G, but since it contains less edges, the sum of the modified edges can be smaller than that in G.

Take for example the following graph:

 A               B
 o-------7-------o
1 \             / 1
   o--2--o--2--o
   C     D     E

Here the shortest path between A and B is through C, D and E, since the sum is 1+2+2+1=6, whereas the direct path between A and B would result in 7.

If we now increase each edge with two for example we obtain:

 A               B
 o-------9-------o
3 \             / 3
   o--4--o--4--o
   C     D     E

So now the path A-C-D-E-B has weight 3+4+4+3=14, whereas the direct path A-B has weight 9. So if we increase each edge with a certain constant, the optimal path can be different.