2

ノード s からノード t へのすべての最短パスを見つけるために使用できる組み込み関数が graph_tool にあるかどうか疑問に思っていました。

そうでない場合、shortest_distance() (モジュール graph_tool.topology 内) または shortest_path() (モジュール graph_tool.topology 内) を何らかの方法で (または他の組み込み関数で) 使用して、代わりにすべての最短パスを計算する方法はありますか?それらのうちの1つだけを効率的に(私は約50万のノードを持つグラフで作業しています)。

4

1 に答える 1

0

グラフツールにはそのような機能はありません。最短経路の数はグラフのサイズと組み合わせて増加するため、一般に、大きなグラフですべての最短経路を見つけることはおそらく不可能であることに注意してください。


UPDATE :all_shortest_paths()関数は最近ライブラリに追加されました。これは、要求されたことを正確に実行します。

https://graph-tool.skewed.de/static/doc/topology.html#graph_tool.topology.all_shortest_paths

于 2014-09-27T08:18:13.533 に答える