Edited at

Networkxを使ったグラフ内パス検索

More than 1 year has passed since last update.


個人的なメモです:


グラフの作成

いちいち書くのはめんどくさいので、隣接リストの形式で作成

import networkx as nx

g = nx.read_adjlist('/path/to/adjacencylist', create_using=nx.DiGraph())
print('nodes: ' + ', '.join(g.nodes()))

print文を追加したことによってgraph内のnodeを全て表示します。


最短経路の検索

もし重みなどを追加した場合は別に必要ですが、ここでは単純のために重みは考えません。

nx.shortest_path(g, source="hoge", target="fuga")

返り値はnodeが入ったリストとなります


ノードに1回だけ訪れたの経路の列挙

for path in nx.all_simple_paths(g, source='hoge", target="fuga"):

print(path)

遠回りの経路も表示してくれます。