Я использую пакет networkx Python.
Python: как найти, существует ли путь между двумя узлами в графе?
Ответ 1
>>> 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"
...
>>>
Ответ 2
Чтобы проверить, существует ли путь между двумя узлами в графе -
>>> 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 — Документация NetworkX 1.7
Ответ 3
Использование структуры данных непересекающихся множеств:
Создайте одноэлементный набор для каждой вершины в графе, затем объедините множества, содержащие каждую пару вершин для каждого ребра в графе.
Наконец, вы знаете, что существует путь между двумя вершинами, если они находятся в одном наборе.
См. страницу wikipedia в структуре данных непересекающихся множеств.
Это намного эффективнее, чем использование алгоритма поиска пути.
Ответ 4
Используйте
shortest_path(G, source, target)
или один из методов Shortest Path. Оставайтесь в стороне от методов, которые возвращают пути между всеми узлами, однако, если у вас есть только два конкретных узла для проверки возможности подключения.
Ответ 5
-
dijkstra_path(G, source, target)
Возвращает кратчайший путь от источника к цели в взвешенном графе G.