python - Python：グラフ内の2つのノード間にパスが存在するかどうかを確認するにはどうすればよいですか？

Question

Pythonのnetworkxパッケージを使用しています。

Answer 1

グラフ内の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 —NetworkX1.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

素集合データ構造の使用：

グラフ内のすべての頂点に対してシングルトンセットを作成してから、グラフ内のすべてのエッジの頂点のペアのそれぞれを含むセットを結合します。

最後に、2つの頂点が同じセットにある場合、それらの間にパスが存在することがわかります。

素集合データ構造に関するウィキペディアのページを参照してください。

これは、パスファインディングアルゴリズムを使用するよりもはるかに効率的です。

Answer 4

使用する

shortest_path(G, source, target)

または最短経路法の1つ。ただし、接続をテストする特定のノードが2つしかない場合は、すべてのノード間のパスを返すメソッドを避けてください。

Answer 5

• dijkstra_path(G, source, target)

  重み付きグラフGでソースからターゲットへの最短経路を返します。