Python: Как найти, существует ли путь между 2 узлами в графике?

Question

Python: Как найти, существует ли путь между 2 узлами в графике?

Я использую networkx пакет Python.

17

python networkx

задан Bruce 1 March 2010 в 03:41

3 ответа

Используйте

shortest_path(G, source, target)

или один из методов кратчайшего пути. Однако избегайте методов, которые возвращают пути между всеми узлами, если у вас есть только два конкретных узла для проверки возможности подключения.

7

ответ дан 30 November 2019 в 10:36

dijkstra_path (G, source, target)

Возвращает кратчайший путь от источника к цели на взвешенном графе G.

3

ответ дан 30 November 2019 в 10:36

Другие вопросы по тегам:

python networkx

Похожие вопросы:

score 13 · Accepted Answer

>>> import networkx as nx
>>> G=nx.empty_graph()
>>> G.add_edge(1,2)
>>> G.add_edge(2,3)
>>> G.add_edge(4,5)
>>> nx.path.bidirectional_dijkstra(G,1,2)
(1, [1, 2])
>>> nx.path.bidirectional_dijkstra(G,1,3)
(2, [1, 2, 3])
>>> nx.path.bidirectional_dijkstra(G,1,4)
False
>>> nx.path.bidirectional_dijkstra(G,1,5)
False
>>>

Вы также можете использовать результат как логическое значение

>>> if nx.path.bidirectional_dijkstra(G,1,2): print "path exists"
... 
path exists
>>> if nx.path.bidirectional_dijkstra(G,1,4): print "path exists"
... 
>>>