I know that this problem is a known NP-Complete problem, but I'm curious as to why a particular algorithm won't work. Given a graph $G = (V,E)$, and edge weights $w(e)$, why can we not create a new graph $G' = (V,E')$, and flip the sign of each edge weight, i.e set the weight of each edge $e' \in E'$ to $w(e') = 0-w(e)$ and use an algorithm such as Bellman-Ford to find the minimum weight path on this new graph. I understand that flipping the sign of the edges could create negative cycles, implying there is no shortest path in $G'$, but won't this imply that there is a positive cycle in $G$, meaning there is no longest path? Can someone give a counter-example of when this algorithm would fail?

  • 1
    $\begingroup$ Have you tried on a simple graph that has a cycle? $\endgroup$ – John L. Jan 8 '19 at 11:56

There's a problem with terminology here. A walk in a graph is a sequence $v_1\dots v_k$ of vertices such that $v_1v_2, v_2v_3, \dots, v_{k-1}v_k$ are edges. A path is a walk that doesn't repeat vertices. So, a graph with a positive-weight cycle contains no longest walk (you can always walk around the cycle one more time to get a longer one) but it does contain a longest path (paths can't go all the way around cycles).

Algorithms such as Bellman–Ford actually compute shortest walks between vertices and use the fact that, as long as the graph has no negative cycles, the shortest walk is also the shortest path. (Any walk that isn't a path must contain a cycle and, if all cycles have positive weight, then the walk without that cycle is shorter.) The graph your algorithm generates contains negative-weight cycles, so Bellman–Ford will fail: it can't use its "the shortest walk is also the shortest path" rule because there is no shortest walk.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.