这篇文章最初发布到 stackoverflow ( https://stackoverflow.com/questions/57315017/best-way-to-include-weights-in-a-directed-acyclic-graph ) 很抱歉长链接，goo.gl 无法缩短它。

有人推荐我把它贴在这个论坛上，因为它看起来更合适。

我正在写我的论文，其中包括编写一个禁忌搜索算法来解决灵活的工作车间问题。为了解决这个问题，我使用图作为问题/解决方案表示（问题是无向图，必须将其转换为有向无环图）。

简而言之，我有一个开始（0）和结束（*）节点，它们是“虚拟”操作，其权重/持续时间为 0。节点代表操作，路径代表处理操作的机器，所以边的长度(u,v) 是在给定机器上交换操作 u 和 v 时产生的设置时间。节点的权重应该是该操作在分配给它的机器上的处理时间。在有向无环图中，从 0 到 * 的最长路径的长度表示解决方案的制造时间（最大生产时间）。

为了实现这一点，我使用了 networkx 库。进展顺利，但我遇到了一些问题，即在计算制造跨度时。首先，由于我发现的函数(dag_longest_path() and dag_longest_path_length())没有考虑节点权重，我将节点权重转移到它们之前的边上。这似乎解决了问题。但是，我刚刚注意到，如果图形是 DiGraph 或 MultiDiGraph，这些函数具有不同的输出，如下所示。

在展示代码之前，请原谅我在这里的菜鸟，第一次发帖。我使用的实例由 30 个操作和 8 台机器组成，但为了简单起见，我将展示一个包含 5 个操作和 3 台机器的简单示例。

import networkx as nx

operations = (1,2,3,4,5)
G=nx.DiGraph()
G.add_node(0,pos=(0,0)) #starting node
G.add_node('*',pos=(1,0)) #end node

G.add_nodes_from(operations)

G.add_edge(0,1, weight = 500)
G.add_edge(1,2, weight = 200)
#these edges are for one machine

G.add_edge(0,3, weight = 150)
G.add_edge(3,4, weight = 177)

#these are for a second machine

G.add_edge(0,5, weight = 999)
#this edge is for the last machine

G.add_edge(2, '*', weight = 0)
G.add_edge(4, '*', weight = 0)
G.add_edge(5, '*', weight = 0)
#edges connecting final operation of each machine to the end node

print(nx.dag_longest_path(G))
print(nx.dag_longest_path_length(G))
#printing the longest path and corresponding length

前面的代码输出以下内容：

[0, 5]
999

这是意料之中的，因为通过节点 5 的路径确实是最长的路径。但是，它不显示结束节点“*”。

如果我用 G=nx.MultiDiGraph() 代替 G=nx.DiGraph()，则输出如下：

[0, 1, 2, '*']
3

现在包含了“*”节点，这是理所当然的，但是返回的路径是具有最多节点的路径，而不是具有最长边的路径。

我在这里想念什么？MultiDiGraph() 在这里似乎是正确的图形类型，因为节点 0 和 '*' 都有多个边离开/进入它们。

我需要一种输出方式：

[0, 5, '*']
999

先感谢您！

PS：请随时纠正格式和演示中的任何错误，因为这是我的第一篇文章