Networkx

で最短経路を選択するの曖昧私はグラフがあります：出力パスが[0, 3, 6]あるのはなぜNetworkx

nx.shortest_path(g, 0, 6)

：

なぜ最短経路の機能を使用した後は？どうしてですか[0, 2, 6]？上記の場合、アルゴリズムshortest_path()のパス[0, 3, 6]の選択は常に明白ですか？

出典

2017-12-30 Tomasz Przemski

「曖昧さがない」とはどういう意味ですか？これは、検索順序で最初に見つかったパスになります。異なる順序でノードを接続するか、エッジのストレージの基礎となる実装が変更された場合、ノード2を経由するルートが最初に試される可能性があります。 –

おそらく、エッジを指定する順序によって異なります。したがって、同じグラフは異なる最短経路を持つことができます。あなたは常に最短経路の* 1 *を取得します。 –

networkxコードを見ると、隣接関係リストへの順序付けを意味するのか、それとも別のものを使用するのかなど、より詳細な情報が提供されます。 –

@ jon-clementsは、質問に対するコメントに正しい答えがあります。 2つ以上の最短経路がある場合、関数networkx.shortest_path()はそれらの1つを返します。あなたが得る特定のパスは、データがnetworkxグラフデータ構造（Python辞書ベース）にどのように格納され、確定的であることが保証されていないかに依存します。あなたが好きな場合は最短経路をすべて取得することができ、安定した注文を提供するために並べ替えることさえできます。

In [1]: import networkx as nx 

In [2]: G = nx.Graph({0: [3, 2], 2: [6, 4], 3: [5, 6]}) 

In [3]: nx.shortest_path(G, 0, 6) 
Out[3]: [0, 2, 6] 

In [4]: list(nx.all_shortest_paths(G, 0,6)) 
Out[4]: [[0, 3, 6], [0, 2, 6]] 

In [5]: sorted(nx.all_shortest_paths(G, 0,6)) 
Out[5]: [[0, 2, 6], [0, 3, 6]]

出典

2017-12-30 20:11:28 Aric

答えて

関連する問題