1

我需要一种算法来在有向无环图中找到最长的加权路径networkx.MultiDiGraph()。我的图有加权边，许多边有一个空值作为权重。在networkx doc中，我没有找到任何解决此问题的方法。我的图表具有以下结构：

>>> 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}}

我找到了她，但我在实施时遇到了问题：

  1. networkx：在有向图中有效地找到绝对最长的路径这个解决方案没有加权。
  2. 如何使用 Python NetworkX 找到最长的路径？该解决方案将权重转换为负值，但我的图表具有空值……并且nx.dijkstra_path()不支持负值。

有没有人找到类似问题的想法或解决方案？

4

1 回答 1

0

采取链接中的解决方案1并更改行：

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

类似于：

pairs = [[dist[v][0]+edge['weight'],v] for u, edge in G[v][node] for v in G.pred[node]] # incoming pairs
于 2015-06-19T12:05:35.703 回答