NetworkXで最短経路探索

せっかくgraphvizではなくNetworkXを動かしているので、何か実装されているアゴリズムを試しておこうというのが今回の趣旨です。
とりあえずグラフ中の二点間の最短経路を探す関数を試してみましょう。
(SNSのフォローや友達関係のネットワークで共通の知り合い等を探すのに使えますね)

まず、ランダムにグラフデータを作成します。

import networkx as nx
import matplotlib.pyplot as plt
import numpy as np

G = nx.Graph()

for i in range(30):
    for j in range(i+1, 30):
        # 1/10の確率でnode間を線で結ぶ
        if np.random.randint(10) == 0:
            G.add_edge(i, j)

# 可視化
fig = plt.figure(figsize=(8, 8))
nx.draw_networkx(G)

出来上がったのはこちら。

ここで2点を指定して、最短経路を求めるにはshortest_pathを使います。
ドキュメント:Shortest Paths

パスが存在しない時にshortest_pathを実行するとエラーになるので、
パスの存在を判定する関数も合わせて試してみます。

# 特定の２つのnode間の最短経路を探す
print(nx.shortest_path(G, source=9, target=20))
# [9, 10, 13, 24, 12, 20]

# source か target を省略すると、その点と他の各点の最短経路を求める
print(nx.shortest_path(G, source=5))
# {5: [5], 6: [5, 6], 29: [5, 29], 21: [5, 6, 21]}

# パスが存在するか判定する
print(nx.has_path(G, source=6, target=10))
# False