networkx: efficiently find absolute longest path in digraph
There is a linear-time algorithm mentioned at http://en.wikipedia.org/wiki/Longest_path_problem Here is a (very lightly tested) implementation EDIT, this is clearly wrong, see below. +1 for future testing more than lightly before posting import networkx as nx def longest_path(G): dist = {} # stores [node, distance] pair for node in nx.topological_sort(G): pairs = [[dist[v][0]+1,v] for v in … Read more