# Max Weight Path in a Graph

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?

• Have you tried on a simple graph that has a cycle? – Apass.Jack Jan 8 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).