从源节点查找DAG上的最长路径

Question

我试图从顶点0找到DAG的最长路径。在Stackoverflow上搜索之后，我了解到我可以反转边的权重，并使用Bellman-Ford算法来找到最长路径。然而，我不完全明白这是怎么回事。在

但是我的图没有权重（都是相等的），我想我应该设置为-1？在

我使用networkx和python来解决这个问题。这是我的行李员代码：

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

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

Answer 1

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

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

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

^{pr2}$

请注意，与使用'myWeight'这样的“自定义”属性不同，您还可以将默认属性'weight'设置为-1，然后调用Bellman Ford，而不必显式指定weight参数。在