Find Longest Weighted Path from DAG with Networkx in Python?

Question

I need a algorithm for find the longest weighted path in a directed, acyclic graph networkx.MultiDiGraph(). My graph has weighted edges and many edges have a null value as the weighting. In networkx doc I have found nothing for solve this problem. My graph has the following structure:

>>> print graph.nodes()
[0, 1, 2, 3, 4, 5, 6, 7, 8, 10, 11, 12, 13, 15, 16, 17, 20, 21, 22, 25, 26, 'end']
>>> print graph.edges()
[(0, 'end'), (1, 0), (1, 10), (1, 5), (2, 1), (2, 11), (2, 6), (3, 2), (3, 12), (3, 7), (4, 8), (4, 3), (4, 13), (5, 'end'), (6, 5), (6, 15), (7, 16), (7, 6), (8, 17), (8, 7), (10, 'end'), (11, 10), (11, 20), (11, 15), (12, 16), (12, 11), (12, 21), (13, 17), (13, 12), (13, 22), (15, 'end'), (16, 25), (16, 15), (17, 16), (17, 26), (20, 'end'), (21, 25), (21, 20), (22, 26), (22, 21), (25, 'end'), (26, 25)]
>>> print graph.edge[7][16]
{1: {'weight': 100.0, 'time': 2}}
>>> print graph.edge[7][6]
{0: {'weight': 0, 'time': 2}}

I find this her, but I have problems with the implementation:

1. networkx: efficiently find absolute longest path in digraph this solution is without weightings.
2. How to find the longest path with Python NetworkX? This solution transformed the weightings into negativ values, but my graph has null values… and the nx.dijkstra_path() does not support negative values.

Have anyone an idea or a solution to a similar problem found?

Answer 1

Take the solution in the link 1 and change the line:

pairs = [[dist[v][0]+1,v] for v in G.pred[node]] # incoming pairs

To something like:

pairs = [[dist[v][0]+edge['weight'],v] for u, edge in G[v][node] for v in G.pred[node]] # incoming pairs