Лучший способ включить веса в направленный ациклический граф ⇐ Python

[Anonymous]

Я пишу алгоритм поиска табу для решения проблемы гибкого магазина вакансий. Я использую графы в качестве представления проблемы/решения (проблема — это ненаправленный граф, который необходимо превратить в направленный ациклический граф).
У меня есть начальный (0) и конечный (*) узлы, которые представляют собой «фиктивные» операции, вес/длительность которых равна 0. Узлы представляют операции, а пути представляют машины, на которых обрабатываются операции, поэтому длина ребра (u,v) — это время установки, необходимое при переключении между операциями u и v в заданном машина. Вес узла должен соответствовать времени обработки этой операции на назначенной ему машине. В направленном ациклическом графе длина самого длинного пути от 0 до * представляет собой период изготовления (максимальное время производства) решения.
Я использую библиотеку networkx. У меня возникли проблемы, а именно при вычислении длины пути.
Поскольку найденные мной функции (dag_longest_path() и 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


Подробнее здесь: https://stackoverflow.com/questions/573 ... clic-graph