PythonのNetworkXパッケージを使って重み付き有向グラフの最短経路をダイクストラ法で求める

Pythonのネットワーク計算パッケージ「NetworkX」を使用して重み付き有向グラフの最短経路をダイクストラ法で求めます。

NetworkXのインストール

下記のようにpipでインストールができます。

pip install networkx

今回はNetworkX2.2を使用しました。

グラフ

下図のノードAからノードEまでの最短経路を求めます。 有向グラフのため矢印を逆戻りすることはできません。

コード

# coding:utf-8

import networkx as nx

# ノード（頂点）のリスト
NODE_LIST = ["A", "B", "C", "D", "E"]

# エッジ（辺）のリスト
# (始点, 終点, 重み)
EDGE_LIST = [
    ("A", "B", 2),
    ("A", "C", 5),
    ("A", "D", 9),
    ("B", "C", 2),
    ("B", "D", 7),
    ("C", "D", 4),
    ("D", "E", 1)
]

# グラフの定義
DG = nx.DiGraph()
DG.add_nodes_from(NODE_LIST)
DG.add_weighted_edges_from(EDGE_LIST)

# 出発地ノードと目的地ノードを設定
start = "A"
end = "E"

# ダイクストラ法で最短経路とその重みを求める
shortest_path = nx.dijkstra_path(DG, start, end)
shortest_path_weight = nx.dijkstra_path_length(DG, start, end)

# 出力
print("Shortest Path:", shortest_path)
print("Weight:", shortest_path_weight)

出力結果

最短経路とその重みを求めることができました。

Shortest Path: ['A', 'B', 'C', 'D', 'E']
Weight: 9