最短経路問題 NetworkX

最短経路問題

NetworkXを使って簡単な最短路問題を解いてみましょう。

例えば、以下のようなグラフがあるとします。

[単純なグラフ]

このグラフにおいて、ノードAからノードDまでの最短経路を求めるソースコードは以下のようになります。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
import networkx as nx

# グラフを定義する
G = nx.Graph()
G.add_edge('A', 'B', weight=5)
G.add_edge('A', 'C', weight=3)
G.add_edge('B', 'D', weight=2)
G.add_edge('C', 'D', weight=3)

# ノードAからノードDまでの最短経路を求める
path = nx.shortest_path(G, 'A', 'D', weight='weight')
print(path)  # 結果：['A', 'C', 'D']

最短経路を求めるために、NetworkXのshortest_path関数を使っています。

またweightパラメータには、辺の重み（コストや所要時間など）を指定しています。

[実行結果]

['A', 'C', 'D']

‘A’ ⇒ ‘C’ ⇒ ‘D’という最短経路を求めることができました