问MultiDiGraph与DiGraph的区别

EN

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

有人建议我把它张贴在这个论坛，因为它似乎更合适。

我正在研究我的论文，其中包括编写一个禁忌搜索算法来解决一个灵活的作业车间问题。为了解决这个问题，我使用图作为问题/解表示(这个问题是一个无向图，必须转化为一个有向无圈图)。

简而言之，我有一个start ( 0 )和end (*)节点，它们是权重/持续时间为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.DiGraph()而不是G=nx.MultiDiGraph()，则输出如下：

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

现在包含了'*‘节点，这是正确的，但是返回的路径是具有大多数节点的路径，而不是具有最长边的路径。

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

我需要一个输出的方法：

[0, 5, '*']
999

提前谢谢你！

PS:请随时更正格式和显示上的任何错误，因为这是我的第一篇文章。