python - 查找 DAG 上从源节点出发的最长路径

Question

我试图找到从顶点0开始的DAG的最长路径。在Stackoverflow上搜索后，我了解到我可以反转边的权重并使用贝尔曼福特算法来找到最长路径。但是，我不完全理解这是如何工作的。

但是我的图表没有权重(全部相等)，我认为我应该设置为 -1？

我正在使用networkx和python来解决这个问题。这是我的贝尔曼代码:

def Bellman(G):
    pred, dist = nx.bellman_ford(G, 0, weight='-1')
    print(dist)

无论我设置什么权重，我仍然得到每个节点从 0 开始的最小距离。我哪里出错了？

Answer 1

根据networkx documentation ，bellamn_ford 的权重参数是包含权重的边属性的键。我猜想通过将其设置为不存在的边缘属性'-1'，它不会考虑任何权重。要完成这项工作，您需要创建一个边缘属性，并将所有边缘设置为 -1:

for n in G:
  for nbr in G[n]:
    G[n][nbr]['myWeight'] = -1

然后使用此属性作为权重调用 Bellman-Ford:

pred, dist = nx.bellman_ford(G, 0, weight='myWeight')

请注意，您还可以将默认属性 'weight' 设置为 -1，然后调用 Bellman-，而不是使用 'myWeight' 等“自定义”属性。福特无需显式指定重量参数。