---
id: wiki-2026-0508-dijkstra-s-algorithm
title: "Dijkstra's Algorithm"
category: 10_Wiki/Topics
status: verified
canonical_id: self
aliases: [Shortest Path, SPF, 다익스트라]
duplicate_of: none
source_trust_level: A
confidence_score: 0.97
verification_status: applied
tags: [graph, shortest-path, algorithm, priority-queue, OSPF]
raw_sources: []
last_reinforced: 2026-05-10
github_commit: pending
tech_stack:
  language: python
  framework: heapq
---

# Dijkstra's Algorithm

## 매 한 줄
> **"매 single-source shortest path on non-negative weighted graphs — O((V+E) log V) with binary heap"**. 매 1959 Edsger Dijkstra 가 매 30분 coffee shop 에서 발견. 매 2026 OSPF routing, Google Maps, A* heuristic baseline, network flow 의 핵심 building block.

## 매 핵심

### 매 핵심 idea
1. 매 priority queue 에서 가장 작은 tentative distance 의 vertex 추출.
2. 매 incident edge 마다 relax: `if d[u] + w(u,v) < d[v]: d[v] = d[u] + w(u,v)`.
3. 매 visited set 에 추가, 매 빈 큐까지 반복.

### 매 복잡도
- **Binary heap**: O((V+E) log V).
- **Fibonacci heap**: O(E + V log V) — 매 dense 에 유리.
- **Bucket queue (Dial's)**: O(E + V·C) — 매 small integer weights.
- **Array (no PQ)**: O(V²) — 매 dense 에 더 빠름.

### 매 제약
- **음의 weight 금지** — 매 Bellman-Ford 사용.
- **단일 source** — 매 all-pairs 는 Floyd-Warshall O(V³).
- **DAG 면 더 빠름** — 매 topological order O(V+E).

### 매 응용
1. **OSPF / IS-IS**: 매 internet routing protocol 의 link-state computation.
2. **Google Maps**: 매 contraction hierarchies + bidirectional Dijkstra.
3. **Game pathfinding**: 매 A* 의 g-score 가 Dijkstra (h=0).
4. **Network analysis**: 매 betweenness centrality 매 계산.

## 💻 패턴

### Standard Implementation (Python)
```python
import heapq
def dijkstra(graph, source):
    dist = {v: float('inf') for v in graph}
    dist[source] = 0
    pq = [(0, source)]
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]: continue          # stale entry
        for v, w in graph[u]:
            nd = d + w
            if nd < dist[v]:
                dist[v] = nd
                heapq.heappush(pq, (nd, v))
    return dist
```

### With Path Reconstruction
```python
def dijkstra_path(graph, src, dst):
    dist = {src: 0}; prev = {}
    pq = [(0, src)]
    while pq:
        d, u = heapq.heappop(pq)
        if u == dst: break
        if d > dist.get(u, float('inf')): continue
        for v, w in graph[u]:
            nd = d + w
            if nd < dist.get(v, float('inf')):
                dist[v] = nd; prev[v] = u
                heapq.heappush(pq, (nd, v))
    path, cur = [], dst
    while cur in prev: path.append(cur); cur = prev[cur]
    return [src] + path[::-1] if dist.get(dst) else None
```

### Bidirectional Dijkstra (Maps-style)
```python
def bidirectional_dijkstra(g, s, t):
    df, db = {s: 0}, {t: 0}
    pf, pb = [(0, s)], [(0, t)]
    visited_f, visited_b = set(), set()
    best = float('inf'); meet = None
    while pf and pb:
        # alternate forward/backward expansion
        if pf[0][0] + pb[0][0] >= best: break
        # ... expand both, update best when meet
    return best, meet
```

### A* (Dijkstra + heuristic)
```python
def a_star(graph, src, dst, h):
    g = {src: 0}; pq = [(h(src, dst), 0, src)]
    while pq:
        f, gu, u = heapq.heappop(pq)
        if u == dst: return gu
        for v, w in graph[u]:
            ng = gu + w
            if ng < g.get(v, float('inf')):
                g[v] = ng
                heapq.heappush(pq, (ng + h(v, dst), ng, v))
```

### Dial's Bucket Algorithm (small int weights)
```python
def dial_dijkstra(graph, src, max_weight):
    n = len(graph); C = max_weight * n + 1
    buckets = [[] for _ in range(C)]
    dist = [float('inf')] * n; dist[src] = 0
    buckets[0].append(src)
    for d in range(C):
        while buckets[d]:
            u = buckets[d].pop()
            if d > dist[u]: continue
            for v, w in graph[u]:
                nd = d + w
                if nd < dist[v]:
                    dist[v] = nd; buckets[nd].append(v)
    return dist
```

### NetworkX (Practical)
```python
import networkx as nx
G = nx.DiGraph()
G.add_weighted_edges_from([('A','B',3), ('B','C',1), ('A','C',5)])
length = nx.dijkstra_path_length(G, 'A', 'C')
path = nx.dijkstra_path(G, 'A', 'C')  # ['A','B','C'] (cost 4)
```

## 매 결정 기준
| 상황 | Approach |
|---|---|
| Non-negative weights, single source | Dijkstra (binary heap) |
| 음의 weight 가능 | Bellman-Ford O(VE) |
| Negative cycle detection | Bellman-Ford |
| All-pairs, dense | Floyd-Warshall O(V³) |
| Heuristic available (e.g., Euclidean) | A* |
| Map-scale (millions of nodes) | Contraction Hierarchies + bidirectional |
| Small integer weights | Dial's buckets |

**기본값**: 매 binary heap Dijkstra — 매 generic, 매 O((V+E) log V) 충분.

## 🔗 Graph
- 부모: [[Graph Theory]] · [[Greedy-Algorithms]]
- Adjacent: [[Topological Sort]]

## 🤖 LLM 활용
**언제**: 매 dependency resolution, 매 chain-of-thought planner 의 minimum-cost reasoning path.
**언제 X**: 매 weights 가 negative 또는 unknown — 매 Bellman-Ford or simulated annealing.

## ❌ 안티패턴
- **Negative weight 적용**: 매 silent wrong answer — 매 항상 Bellman-Ford 사용.
- **Lazy deletion 누락**: 매 PQ 의 stale entry 미처리 → infinite loop 가능.
- **Recomputing every query**: 매 static graph 면 precompute (CH) 또는 caching.
- **Naive O(V²) on sparse graph**: 매 V=10⁶ 면 O((V+E) log V) 필수.

## 🧪 검증 / 중복
- Verified (CLRS Ch.24; Dijkstra 1959 *Numerische Mathematik*; NetworkX 3.x docs).
- 신뢰도 A.

## 🕓 Changelog
| 날짜 | 변경 |
|---|---|
| 2026-05-08 | Phase 1 |
| 2026-05-10 | Manual cleanup — full content with heap, A*, bidirectional patterns |
