Кратчайший путь в сети с «ключевыми» узлами для посещения

Question

У меня есть ориентированный граф на python G, разработанный с помощью networkx.Граф имеет весовые коэффициенты, называемые «вес».

Я знаю явный начальный узел A и конечный узел F. Между графиком можно получить доступ к узлам B, C, D, E.

Как я могу ясно сказать, что он должен получить доступ к B и D путем нахождения кратчайшего пути и может дополнительно добавлять C и E, если это помогает к кратчайшему пути?

Пока я знаю функцию:

nx.single_source_dijkstra(G, 'A', target='F', cutoff=None, weight='weight')

, который дает вывод:

(10.01,
['A',
 'B',
 'C',
 'F',])

Как я могу убедиться, что он включает E?

Answer 1

Networkx не имеет встроенных функций или аргументов для вашей проблемы.Вы должны сделать это вручную:

import networkx as nx

# Create a random DAG
G = nx.gnp_random_graph(50,0.3,directed=True)
DAG = nx.DiGraph([(u,v) for (u,v) in G.edges() if u<v])
nx.is_directed_acyclic_graph(DAG)
for edge in G.edges:
    G.edges[edge]['weight'] = 1

# Get the longest path (without weights) from node 1 to node 40
# with nodes 5, 10, 20, 30 inside
max([
    (path, len(path))
    for path in nx.all_simple_paths(DAG, 1, 40)
    if all(n in path for n in (5, 10, 20, 30))
], key=lambda x: x[1])

# Get the longest path (with weights)
max([
    path
    for path in nx.all_simple_paths(DAG, 1, 40)
    if all(n in path for n in (5, 10, 20, 30))
], key=lambda x: sum(G.edges[edge]['weight'] for edge in nx.utils.pairwise(x)))