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

[Ananya Muddukrishna]

Thank you, Tamás,  for the quick and great reply!

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.
So technically, it should be possible to implement a function that supports negative weights on my own?
I ask because I have a newcomers understanding of graph algorithms.

On 11/19/2013 09:05 PM, Tamás Nepusz wrote:

Hi,

The get.shortest.paths function fails complaining about negative edge

weights.

That’s no wonder - get.shortest.paths is meant for finding the *shortest* path between two vertices, and if you happen to have a cycle in your graph where the total edge weight sum is negative, then the shortest path would be infinite.

In general, longest paths only make sense in graphs if you also specify some restrictions; for instance, you could specify that no vertex or no edge can be traversed twice on the path (otherwise the longest path would be any infinite walk on the graph). An alternative restriction could be that you only want to do this for directed acyclic graphs; in this case, you could do this with all the weights negated because the graph guarantees that there are no cycles.

My example graph is directed with negated weights.
So the second restriction you mention applies in my case.

However, get.shortest.paths() would still not work because it uses Dijkstra’s algorithm for finding the paths and Dijkstra’s algorithm does not support weights.

Is negative-weight support planned for get.shortest.paths?

You may try shortest.paths(algorithm=“bellman-ford”) instead, but this won’t return the path itself for you, only the distances.

I will stick with shortest.paths(algorithm=“bellman-ford”) for now.

— 

T.

_______________________________________________
igraph-help mailing list
address@hidden
https://lists.nongnu.org/mailman/listinfo/igraph-help

Best regards,
Ananya

Ananya Muddukrishna
Ph.D. student
KTH Royal Institute of Technology
http://www.kth.se/profile/ananya/