はじめに

2頂点対最短経路問題を解いている時に、最短ではないが条件を満たすパスの見つけ方を調べたので、メモとして残しておきます。

手順

1. 隣接行列の作成

今回のデータは.csv fileに保存されているのでpandasを使って読み取り、numpy arrayに変換します。

file = pd.read_csv('Data1.csv', header=None, delimiter=',')  
data = np.array(file)

2. NetworkXでグラフを作成する。

NetworkXは、グラフ/ネットワーク理論系の計算を行うためのPythonのパッケージです。

G=nx.from_numpy_matrix(data)

3. 指定した２点間をつなぐ全てのパスを探し、プリントする。

使用した関数はnx.all_simple_paths()。この関数は先ほど作成したグラフGにおいて、スタート地点(= source)とゴール地点（= target）を指定することで、指定した２点間をつなぐ全てのパスを探し出します。ただし、有向グラフでない場合、特に巨大なグラフの場合は何万通りものパスを見つけてしまうので、cutoffでパスの深さを限定する必要があります。

for path in nx.all_simple_paths(G,source=1,target=100, cutoff=13): 
	print(path)

結果はこの通りです、
読み込んだデータは8000ノードある巨大なものなので、パスの深さを13に限定しました。

[1, 2587, 808, 211, 188, 6510, 6216, 3057, 5276, 1512, 3826, 5203, 100]
[1, 2587, 808, 4675, 1671, 5411, 3983, 3714, 202, 3064, 644, 2182, 100]
[1, 2587, 808, 4675, 1671, 5411, 3983, 6512, 3590, 7915, 2182, 100]
[1, 2587, 808, 4675, 5958, 4521, 6562, 7430, 4083, 6189, 3089, 3826, 5203, 100]
[1, 2587, 6562, 4521, 5958, 4675, 1671, 5411, 3983, 6512, 3590, 7915, 2182, 100]
[1, 2587, 6562, 6046, 4846, 324, 7374, 1141, 3651, 1963, 888, 5203, 100]
[1, 2587, 6562, 7430, 4083, 6189, 3089, 3826, 5203, 100]
[1, 3346, 4986, 4968, 2652, 1750, 5373, 6453, 6667, 5505, 7572, 7915, 2182, 100]
[1, 3346, 4986, 4968, 2652, 2154, 5437, 656, 3987, 2058, 6764, 6790, 2182, 100]
[1, 3346, 4986, 4968, 2652, 2800, 2448, 3575, 1141, 3651, 1963, 888, 5203, 100]
[1, 3346, 4986, 4968, 4197, 7116, 6733, 869, 4783, 6468, 7620, 6790, 2182, 100]
[1, 3346, 4986, 4968, 5331, 1379, 6246, 6214, 40, 2579, 3590, 7915, 2182, 100]
[1, 3346, 4986, 4968, 5331, 7417, 7969, 6865, 2863, 868, 6764, 6790, 2182, 100]

最後に

コード自体はとてもシンプルですが、一度引っかかったポイントとしてはパスの深さを限定しないでいるとプログラムが終わらないという点です。同じような問題に取り組んでいる方の参考になればと思います。