[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [igraph] Longest path algorithm in igraph?

From: Tamás Nepusz
Subject: Re: [igraph] Longest path algorithm in igraph?
Date: Sat, 16 Jul 2011 18:11:21 +0200

Is there an algorithm computing longest paths in graphs implemented in
igraph or elsewhere?
Not in igraph, unless the graph is acyclic, in which case you can succeed with negating the edge weights and finding the shortest path. If the graph is directed and acyclic, you may also use the topological sorting algorithm which achieves the same. Otherwise, as far as I know, the problem is NP-hard, and there is no implementation for solving this problem in igraph.


reply via email to

[Prev in Thread] Current Thread [Next in Thread]