Graph アルゴリズム入門：最短経路アルゴリズム

はじめに

重み付きグラフにおける代表的な最短経路アルゴリズムとして Dijkstra と Bellman-Ford が挙げられます。

• Dijkstra: 負の辺を含まない（辺の重みが非負）グラフで最短経路を効率よく求められる。
• Bellman-Ford: 負の辺がある場合でも最短経路を求められる。また負閉路（負の重み和を持つ閉路）の検出も可能。

本記事では、Google Colab 上で簡単に試せるサンプルコードを示します。

Google Colab の準備

もしくは、以下のように自身の Colab ノートブックを作成してご活用ください。

1. Google Colab にアクセス。
2. 「新しいノートブック」を作成。
3. 以下のサンプルコードをコピー＆ペーストで実行。

使用ライブラリ

• NetworkX: グラフ構造の操作やアルゴリズムの実行が簡単にできる Python ライブラリ。
• matplotlib: グラフ可視化に利用。

---

サンプルコード：Dijkstra と Bellman-Ford の動作確認

以下のコードを Colab で実行すると、

• NetworkX の single_source_dijkstra (Dijkstra)
• NetworkX の bellman_ford_path_length (Bellman-Ford)
  を使って最短経路を計算し、可視化します。グラフはより見やすい形に改良されています。

!pip install networkx matplotlib
import networkx as nx
import matplotlib.pyplot as plt

# ==============================
# 1. グラフ構築
# ==============================
G = nx.DiGraph()
edges = [
    (0, 1, 2),  # Node 0 -> Node 1, weight=2
    (0, 2, 4),  # Node 0 -> Node 2, weight=4
    (1, 2, 1),  # Node 1 -> Node 2, weight=1
    (1, 3, 7),  # Node 1 -> Node 3, weight=7
    (2, 4, 3),  # Node 2 -> Node 4, weight=3
    (4, 3, -2)  # Node 4 -> Node 3, weight=-2 (負の辺)
]
G.add_weighted_edges_from(edges)

# ==============================
# 2. レイアウト（可視化での位置指定）
# ==============================
pos = {
    0: (0, 0),
    1: (1, 1),
    2: (2, 0),
    3: (3, 1),
    4: (3, -1),
}

# ==============================
# 3. グラフの可視化
# ==============================
plt.figure(figsize=(8, 6))
nx.draw(
    G, pos, with_labels=True, node_color='skyblue', node_size=1000,
    font_size=15, font_color='black', arrowsize=20
)
edge_labels = nx.get_edge_attributes(G, 'weight')
nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels, font_size=12)

plt.title("Sample Graph", fontsize=16)
plt.show()

# ==============================
# 4. Dijkstra で最短経路を計算
# ==============================
try:
    distances_dijkstra, paths_dijkstra = nx.single_source_dijkstra(G, source=0)
    print("=== Dijkstra's result (from node 0) ===")
    for node, dist in distances_dijkstra.items():
        print(f"  0 -> {node}, distance = {dist}, path = {paths_dijkstra[node]}")
    print()
except Exception as e:
    print("Dijkstra による最短経路計算でエラーが発生しました:", e)
    print()

# ==============================
# 5. Bellman-Ford で最短経路を計算
# ==============================
# single_source_bellman_ford_path_length のような関数がない場合は
# bellman_ford_predecessor_and_distance を使って、経路を復元する
pred, dist_bf = nx.bellman_ford_predecessor_and_distance(G, source=0)

# 経路復元用の関数
def retrieve_path(predecessors, start, end):
    """
    predecessors: {ノード: [前ノード]} の辞書
    start: 開始ノード
    end:   終了ノード
    """
    if end not in predecessors and end != start:
        # 到達不可の場合は None などを返す（ここはお好み）
        return None
    path = [end]
    # 前ノードを遡って path を構成
    while path[-1] != start:
        path.append(predecessors[path[-1]][0])
    # 反転してスタート → ゴールの向きに
    path.reverse()
    return path

print("=== Bellman-Ford's result (from node 0) ===")
for node in G.nodes():
    path_bf = retrieve_path(pred, 0, node)
    print(f"  0 -> {node}, distance = {dist_bf[node]}, path = {path_bf}")

---

解説

1. Dijkstra

   • 負の重みを持たないグラフを対象とした最短経路アルゴリズム。
   • 各ステップで「未確定のうち最も距離が小さいノード」を確定していくため、効率よく結果を得られる。

2. Bellman-Ford

   • 負の辺を持つ場合でも最短経路を求められる。
   • すべての辺を「頂点数 - 1」回ループして緩和（relax）し、最短経路が得られる。
   • 「頂点数」回目の緩和でさらに最短距離が改善するなら、負閉路が存在すると判断できる。

---

実行結果例

• ノードの位置が手動で指定されているため、グラフが重ならず見やすい配置になります。
• Dijkstra は負の辺がある場合には正常に動作しない可能性がありますが、負の辺がないグラフでは効率的です。
• Bellman-Ford は負の辺を含む場合でも正しく最短経路を求められ、負閉路があれば検出することが可能です。

---

まとめ

• Dijkstra は「非負重みの辺のみ」のグラフで最短経路を高速に求めたい場合に最適。
• Bellman-Ford は「負の重みがある」場合や、「負閉路が存在するか確認したい」場合に活用できる。

最短経路を求める際は、グラフの性質（負辺の有無）をよく確認し、適切なアルゴリズムを選択することが重要です。