Find Longest Weighted Path from DAG with Networkx in Python?

1
votes

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?

1
pythonalgorithmgraphweightedlongest-path
if nx.dijkstra_path() does not support negative weights, transform weights according to w <-- -w + Wmax where Wmax is the maximum weight in the original graph. - fferri
This does not work because the algorithm continues the shortest path searching… Or I understand this wrong? - Robi Roboter
This does not work because the weight change for each path will depend on the number of edges. - MBW

1 Answers

0
votes

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