Как найти кратчайший путь в сети x без поиска обратно?

Question

У меня есть типичный график, это дерево, и я могу найти кратчайший путь между двумя узлами:

nx.shortest_path(G, source=root, target=target)

Но я не знаю, есть ли простая функция, которая не позволяет выполнять поиск в обратном направлении.То есть, в качестве входных данных:

nx.shortest_path(G, 5, 10)

[5, 6, 10]

он смотрит вперед (вниз по дереву), но если

nx.shortest_path(G, 5, 3)

[5, 3]

он возвращает дерево, но должен дать None.

Мой вопрос: есть ли простой способ выбраться?или мне просто нужно реализовать пользовательскую функцию для проверки этой проблемы?

Answer 1

Как уже упоминалось в комментариях, на графике нет "вверх" или "вниз".Вы можете создать ориентированный граф, используя класс DiGraph(), где вы получаете ошибку «NetworkXNoPath: нет пути между 3 и 1.», когда вы пытаетесь найти путь против направлений ребер.В этом случае вы можете использовать try для перехвата исключения:

import networkx as nx
from networkx import NetworkXNoPath

G = nx.DiGraph([(1, 2), (2, 3), (4,2)]) # create a directed graph

nx.shortest_path(G, source=1, target=3)
# [1, 2, 3]

try:
    path = nx.shortest_path(G, source=3, target=1)
except NetworkXNoPath:
    path = None

В качестве альтернативы вы можете проверить, имеют ли две вершины какой-либо путь вообще:

nx.has_path(G, source=3, target=1)
# False

if nx.has_path(G, source=3, target=1):
    path = nx.shortest_path(G, source=3, target=1)
else:
    path = None