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

我正在尝试从顶点0查找DAG的最长路径。在Stackoverflow上搜索后，我了解到可以反转边的权重并使用Bellman Ford算法来找到最长的路径。但是，我不完全了解它是如何工作的。

但是我的图没有权重（全部相等），我假设我应该设为-1？

我正在使用networkx和python解决此问题。这是我的Bellman代码：

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

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

最佳答案

根据networkx documentation，bellamn_ford的权重参数是包含权重的edge属性的键。我想通过将其设置为不存在的边缘属性'-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')

请注意，除了使用'myWeight'之类的“自定义”属性外，还可以将默认属性'weight'设置为-1，然后调用Bellman-Ford，而不必显式指定weight-Parameter。