DijkstraとBellman-Fordはどのように最短経路を見つけるのか？

Question

Accepted Answer

どちらも加重グラフ内の**ソースからの最短経路**を見つけます。**Dijkstra**はより高速ですが**非負の**重みが必要です。**Bellman-Ford**はより遅いですが**負の**辺を処理でき、負のサイクルを検出します。

## Dijkstra (greedy + min-heap)

繰り返し未訪問の最も近いノードを展開し、その隣接ノードをリラックスします。

```python
import heapq

def dijkstra(graph, src):
    dist = {n: float('inf') for n in graph}
    dist[src] = 0
    pq = [(0, src)]                    # (distance, node)
    while pq:
        d, u = heapq.heappop(pq)       # closest first
        if d > dist[u]:
            continue
        for v, w in graph[u]:
            if d + w < dist[v]:        # relax edge
                dist[v] = d + w
                heapq.heappush(pq, (dist[v], v))
    return dist
```

## Bellman-Ford (DP形式のリラックス)

**すべての**辺をV-1回リラックスします。さらにリラックスできれば、負のサイクルが存在します。

## 比較

| | Dijkstra | Bellman-Ford |
|---|---------|---------------|
| 重み | 非負 | 任意（負を含む） |
| 時間 | O((V+E) log V) | O(V·E) |
| 負サイクル | 該当なし | 検出 |

## 使用時期 / 落とし穴

非負の重みには**Dijkstra**をデフォルトで使用します（マップ、ネットワーク）。負の辺が存在する場合は**Bellman-Ford**を使用します（例えば、アービトラージ）。Dijkstraは負の重みで暗黙的に失敗します。これは典型的な落とし穴です。

## なぜ重要なのか

最短経路アルゴリズムは、ルーティング、ナビゲーション、ネットワークプロトコル、および依存関係のコスト分析を駆動します。

Dijkstraの非負の重みの制約を知ることは、実務での間違った答えを防ぎます。

リラックスのアイデアはグリーディとDP思考をつなぎ、シニアレベルの豊かなトピックになります。

	Dijkstra	Bellman-Ford
重み	非負	任意（負を含む）
時間	O((V+E) log V)	O(V·E)
負サイクル	該当なし	検出