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

Question

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

Answer 1

Чтобы проверить, существует ли путь между двумя узлами в графе -

>>> import networkx as nx
>>> G=nx.Graph()
>>> G.add_edge(1,2)
>>> G.add_edge(2,3)
>>> nx.has_path(G,1,3)
True
>>> G.add_edge(4,5)
>>> nx.has_path(G,1,5)
False

Для получения дополнительной информации см. has_path & mdash; Документация по NetworkX 1.7

Answer 2

>>> 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"
... 
>>> 

Answer 3

Использование непересекающейся структуры данных набора:

Создайте одноэлементное множество для каждой вершины графа, затем объедините множества, содержащие каждую пару пар для каждого ребра графа.

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

См. Страницу wikipedia в структуре данных несвязанных множеств.

Это намного эффективнее, чем использование алгоритма поиска пути.

Answer 4

Использование

shortest_path(G, source, target)

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

Answer 5

• dijkstra_path(G, source, target)

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