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

## はじめに

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

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

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

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2648069/14d50cb0-65fd-064c-9f57-66cdf4464705.png)

## Google Colab の準備

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

1. [Google Colab](https://colab.research.google.com/) にアクセス。  
2. 「新しいノートブック」を作成。  
3. 以下のサンプルコードをコピー＆ペーストで実行。  

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

---

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

以下のコードを Colab で実行すると、  
- NetworkX の `single_source_dijkstra` (Dijkstra)  
- NetworkX の `bellman_ford_path_length` (Bellman-Ford)  
を使って最短経路を計算し、可視化します。グラフはより見やすい形に改良されています。

```python
!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}")

```

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2648069/a0c7fba4-811c-49d3-61ed-9588d07ad768.png)

---

## 解説

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

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

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2648069/e2497c10-6b92-14a2-fcef-7357063e7d6a.png)

---

## 実行結果例

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

---

## まとめ

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

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

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2648069/3e511986-c3f9-da95-fab1-05f22f8b8cfd.png)