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

[Tamás Nepusz]

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

— 

T.