Thank you for your detailed answers!
I now understand that trying to hack the shortest path algorithm by
negating weights is not a good idea.
I will find a way to directly solve the problem.
Long live igraph!
Best regards,
Ananya
On 11/19/2013 10:53 PM, Tamás Nepusz wrote:
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.
_______________________________________________
igraph-help mailing list
[email protected]
https://lists.nongnu.org/mailman/listinfo/igraph-help
Ananya Muddukrishna
Ph.D. student
KTH Royal Institute of Technology
http://www.kth.se/profile/ananya/
_______________________________________________
igraph-help mailing list
[email protected]
https://lists.nongnu.org/mailman/listinfo/igraph-help
