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

Question

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

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

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

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')

请注意，除了使用 'myWeight' 之类的 "custom" 属性，您还可以将默认属性 'weight' 设置为 -1，然后调用 Bellman-Ford 而无需显式指定权重参数。