Re: [igraph] Longest path calculation complains about negative edge weights

[Tamás Nepusz]

I read about the longest path problem (http://en.wikipedia.org/wiki/Longest_path_problem) and did not find any limitations regarding negative weights in directed graphs.

Well, because negative weights in a graph in which you search for the longest path in general does not present a problem at all. Your problem is that you are trying to find the longest path in a graph by *negating* the weights and then running a *shortest* path algorithm. This won’t work because shortest path algorithms run in polynomial time while the longest path problem is NP-hard.

 

So technically, it should be possible to implement a function that supports negative weights on my own?

Yes, but that won’t solve the longest path problem. Consider a ring graph with four nodes: A, B, C and D. Let us assume that all the edges have equal weight (i.e. weight=1). The longest path from A to B is then A-D-C-B, which has length 3, and it is easy to see that there cannot exist any longer path (unless you allow repetitions of vertices, in which case the longest path is infinite). Now, negate all the weights in the graph and try to apply a shortest path algorithm. The shortest path algorithm would then get stuck in an infinite loop because it will go from A to D, then back to A, then back to D, then back to A and so on since each step _decreases_ the total path weight by 1 (remember, all the weights are now -1), and this can continue till infinity.

 

T.