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
address@hidden
https://lists.nongnu.org/mailman/listinfo/igraph-help