Dijkstra — Đường đi ngắn nhất từ một nguồn

Mỗi khi bạn mở Google Maps tìm đường, mỗi khi router chạy OSPF để chuyển gói tin, mỗi khi NPC trong game tìm đường đến mục tiêu — Dijkstra đang chạy ở đằng sau. Đây là thuật toán shortest path được deploy nhiều nhất trong production, từ hệ thống GPS đến network routing protocol.

Dijkstra giải bài toán: cho đồ thị có trọng số không âm, tìm đường đi ngắn nhất từ một đỉnh nguồn đến tất cả các đỉnh còn lại. Kết quả là mảng dist[] — bản đồ khoảng cách hoàn chỉnh từ nguồn.

Bức tranh tư duy

Hình dung ngọn lửa bùng cháy từ một điểm trên cánh đồng khô. Lửa lan ra mọi hướng, nhưng đỉnh gần nhất bắt lửa trước — đúng theo greedy principle. Khi một đỉnh đã cháy (đã được xử lý), khoảng cách đến nó là tối ưu và không bao giờ thay đổi.

Bước 1: Lửa tại A (dist=0)
    A(0) ---3--- B(∞)
    |            |
    7            1
    |            |
    D(∞) ---2--- C(∞)

Bước 2: B bắt lửa (dist=3, gần nhất)
    A(0) ---3--- B(3) ✓
    |            |
    7            1
    |            |
    D(∞) ---2--- C(4)    ← relaxed: 3+1=4

Bước 3: C bắt lửa (dist=4)
    A(0) ---3--- B(3) ✓
    |            |
    7            1
    |            |
    D(6) ---2--- C(4) ✓  ← relaxed: 4+2=6

Bước 4: D bắt lửa (dist=6)
    A(0) ---3--- B(3) ✓
    |            |
    7            1
    |            |
    D(6) ✓ --2-- C(4) ✓

Analogy này breakdown khi đồ thị có trọng số âm — lửa không thể "quay ngược" để rút ngắn khoảng cách đã xác nhận. Đó là lý do Dijkstra yêu cầu trọng số ≥ 0.

Cốt lõi kỹ thuật

Nguyên lý Relaxation

Relaxation là thao tác cốt lõi: nếu đi qua đỉnh u đến v ngắn hơn đường hiện tại đến v, cập nhật.

if dist[u] + weight(u, v) < dist[v]:
    dist[v] = dist[u] + weight(u, v)

Dijkstra đảm bảo mỗi đỉnh được relaxation từ đỉnh có khoảng cách nhỏ nhất chưa xử lý — nhờ priority queue (min-heap).

Lazy Deletion Optimization

Khi relaxation cập nhật dist[v], ta push entry mới (dist[v], v) vào heap thay vì decrease-key (vì binary heap không hỗ trợ decrease-key hiệu quả). Khi pop ra entry (d, u) mà d > dist[u], entry đó đã cũ (stale) — bỏ qua.

Cài đặt đầy đủ

C++

#include <vector>
#include <queue>
using namespace std;

typedef pair<int, int> pii; // {distance, node}

vector<int> dijkstra(int V, const vector<vector<pii>>& adj, int src) {
    vector<int> dist(V, INT_MAX);
    dist[src] = 0;
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    pq.push({0, src});

    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();

        if (d > dist[u]) continue; // Lazy deletion

        for (auto [v, w] : adj[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
    return dist;
}

Python

import heapq

def dijkstra(V: int, adj: list[list[tuple[int, int]]], src: int) -> list[int]:
    """adj[u] = [(v, weight), ...]. Returns dist[] from src."""
    INF = float('inf')
    dist = [INF] * V
    dist[src] = 0
    pq = [(0, src)]  # (distance, node)

    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue  # Lazy deletion

        for v, w in adj[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush(pq, (dist[v], v))

    return dist

Java

import java.util.*;

public class Dijkstra {
    public static int[] dijkstra(int V, List<List<int[]>> adj, int src) {
        int[] dist = new int[V];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[src] = 0;

        // int[] = {distance, node}
        PriorityQueue<int[]> pq = new PriorityQueue<>(
            Comparator.comparingInt(a -> a[0])
        );
        pq.offer(new int[]{0, src});

        while (!pq.isEmpty()) {
            int[] top = pq.poll();
            int d = top[0], u = top[1];

            if (d > dist[u]) continue;

            for (int[] edge : adj.get(u)) {
                int v = edge[0], w = edge[1];
                if (dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                    pq.offer(new int[]{dist[v], v});
                }
            }
        }
        return dist;
    }
}

Go

import "container/heap"

type Item struct{ dist, node int }
type MinHeap []Item
func (h MinHeap) Len() int            { return len(h) }
func (h MinHeap) Less(i, j int) bool   { return h[i].dist < h[j].dist }
func (h MinHeap) Swap(i, j int)        { h[i], h[j] = h[j], h[i] }
func (h *MinHeap) Push(x interface{})  { *h = append(*h, x.(Item)) }
func (h *MinHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[:n-1]
    return x
}

func dijkstra(V int, adj [][]struct{ v, w int }, src int) []int {
    const INF = 1<<31 - 1
    dist := make([]int, V)
    for i := range dist {
        dist[i] = INF
    }
    dist[src] = 0

    h := &MinHeap{{0, src}}
    heap.Init(h)

    for h.Len() > 0 {
        top := heap.Pop(h).(Item)
        d, u := top.dist, top.node

        if d > dist[u] {
            continue
        }
        for _, e := range adj[u] {
            if dist[u]+e.w < dist[e.v] {
                dist[e.v] = dist[u] + e.w
                heap.Push(h, Item{dist[e.v], e.v})
            }
        }
    }
    return dist
}

Truy vết đường đi (Path Reconstruction)

Thêm mảng prev[] để lưu đỉnh cha trên đường đi ngắn nhất.

def dijkstra_with_path(V: int, adj: list[list[tuple[int, int]]], src: int):
    INF = float('inf')
    dist = [INF] * V
    prev = [-1] * V
    dist[src] = 0
    pq = [(0, src)]

    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue
        for v, w in adj[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                prev[v] = u
                heapq.heappush(pq, (dist[v], v))

    return dist, prev

def reconstruct(prev: list[int], dest: int) -> list[int]:
    path = []
    cur = dest
    while cur != -1:
        path.append(cur)
        cur = prev[cur]
    return path[::-1]

Thực chiến

Tình huống 1: GPS Navigation — tìm đường ngắn nhất

Bối cảnh: Hệ thống navigation cần tìm đường ngắn nhất (theo thời gian di chuyển) giữa hai giao lộ trong thành phố. Đồ thị có ~500K đỉnh, ~1.2M cạnh, trọng số là thời gian di chuyển (giây).

Mục tiêu: Response time < 100ms cho mỗi truy vấn.

import heapq

def find_route(graph, start: int, end: int) -> tuple[int, list[int]]:
    """
    Dijkstra cho navigation.
    graph[u] = [(v, time_seconds), ...]
    Returns: (total_time, path)
    """
    V = len(graph)
    dist = [float('inf')] * V
    prev = [-1] * V
    dist[start] = 0
    pq = [(0, start)]

    while pq:
        d, u = heapq.heappop(pq)
        if u == end:
            break  # Early termination: chỉ cần đến đích
        if d > dist[u]:
            continue
        for v, w in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                prev[v] = u
                heapq.heappush(pq, (dist[v], v))

    path = []
    cur = end
    while cur != -1:
        path.append(cur)
        cur = prev[cur]

    return dist[end], path[::-1]

Phân tích: Early termination if u == end: break giảm đáng kể thời gian khi chỉ cần đường đến một đích cụ thể. Trong production, Google Maps kết hợp Dijkstra với A* (thêm heuristic) và contraction hierarchies để xử lý đồ thị hàng trăm triệu đỉnh.

Tình huống 2: Network Routing — OSPF Protocol

Bối cảnh: Giao thức OSPF (Open Shortest Path First) dùng Dijkstra tại mỗi router để tính bảng routing. Trọng số cạnh là bandwidth cost (inversely proportional to bandwidth).

def build_routing_table(router_id: int,
                        topology: list[list[tuple[int, int]]]) -> dict[int, int]:
    """
    Xây dựng routing table: destination → next_hop.
    topology[u] = [(v, cost), ...]
    """
    V = len(topology)
    dist = [float('inf')] * V
    prev = [-1] * V
    dist[router_id] = 0
    pq = [(0, router_id)]

    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue
        for v, cost in topology[u]:
            if dist[u] + cost < dist[v]:
                dist[v] = dist[u] + cost
                prev[v] = u
                heapq.heappush(pq, (dist[v], v))

    # Truy vết: tìm next hop cho mỗi destination
    routing_table = {}
    for dest in range(V):
        if dest == router_id or dist[dest] == float('inf'):
            continue
        cur = dest
        while prev[cur] != router_id:
            cur = prev[cur]
        routing_table[dest] = cur  # next_hop

    return routing_table

Phân tích: Mỗi router chạy Dijkstra trên toàn bộ topology graph. Khi topology thay đổi (link down/up), router tính lại routing table. OSPF chia mạng thành area để giảm kích thước đồ thị mỗi router phải xử lý.

Sai lầm điển hình

❌ Sai lầm 1: Dùng Dijkstra với trọng số âm

Vấn đề: Đồ thị có cạnh trọng số âm, vẫn dùng Dijkstra.

A ---(-2)--- B
|            |
(4)         (3)
|            |
C ----(1)--- D

Dijkstra từ A: chốt B = -2 (greedy, gần nhất).
Nhưng A→C→D→B = 4+1+3 = 8 (đúng ra có thể có đường tốt hơn qua relaxation)
→ Kết quả SAI vì đỉnh đã chốt không bao giờ được xét lại.

Tại sao sai: Dijkstra hoạt động dựa trên bất biến: "đỉnh đã pop khỏi heap có khoảng cách tối ưu". Trọng số âm phá vỡ bất biến này vì cạnh âm có thể tạo đường ngắn hơn qua đỉnh đã chốt.

ĐÚNG: Dùng Bellman-Ford khi có trọng số âm.

❌ Sai lầm 2: Bỏ qua lazy deletion check

Vấn đề: Không kiểm tra d > dist[u] khi pop khỏi heap.

# SAI: thiếu lazy deletion
while pq:
    d, u = heapq.heappop(pq)
    # Thiếu: if d > dist[u]: continue
    for v, w in adj[u]:
        if dist[u] + w < dist[v]:
            dist[v] = dist[u] + w
            heapq.heappush(pq, (dist[v], v))

Tại sao sai: Một đỉnh có thể được push vào heap nhiều lần (mỗi lần relaxation). Không skip entry cũ dẫn đến xử lý cùng một đỉnh nhiều lần — tăng time complexity lên $O(E^2\log E)$ trong worst case.

# ĐÚNG: lazy deletion
while pq:
    d, u = heapq.heappop(pq)
    if d > dist[u]:
        continue  # Entry cũ, bỏ qua
    for v, w in adj[u]:
        ...

❌ Sai lầm 3: Khởi tạo dist sai

Vấn đề: Khởi tạo dist bằng 0 hoặc giá trị nhỏ thay vì vô cùng.

# SAI: dist[i] = 0 cho mọi i
dist = [0] * V

Tại sao sai: Nếu dist[v] = 0 ban đầu, điều kiện dist[u] + w < dist[v] sẽ hiếm khi thỏa mãn → thuật toán gần như không relaxation, trả về kết quả sai.

# ĐÚNG: dist = INF, trừ source = 0
dist = [float('inf')] * V
dist[src] = 0

❌ Sai lầm 4: Dùng max-heap thay vì min-heap

Vấn đề: Quên đảo dấu hoặc quên cấu hình min-heap.

// SAI: C++ priority_queue mặc định là MAX-heap
priority_queue<pii> pq;  // Lấy phần tử LỚN nhất trước!

Tại sao sai: Dijkstra cần xử lý đỉnh gần nhất trước. Max-heap lấy đỉnh xa nhất → kết quả sai.

// ĐÚNG: khai báo min-heap
priority_queue<pii, vector<pii>, greater<pii>> pq;

Under the Hood

Hiệu năng

Cấu trúc heap	Time Complexity	Ghi chú
Binary heap (standard)	$O((V+E)\log V)$	Phổ biến nhất, dùng trong hầu hết production
Mảng (không dùng heap)	$O(V^2)$	Phù hợp dense graph ($E\approx V^2$)
Fibonacci heap	$O(V\log V+E)$	Tối ưu lý thuyết, hiếm khi dùng thực tế

Space complexity: $O(V+E)$ cho adjacency list + $O(V)$ cho dist/prev + $O(E)$ worst case cho heap.

Nội bộ triển khai

Tại sao binary heap phổ biến hơn Fibonacci heap? Fibonacci heap có amortized $O(1)$ decrease-key thay vì $O(\log V)$, nhưng constant factor lớn và cài đặt phức tạp. Trên thực tế, binary heap + lazy deletion nhanh hơn Fibonacci heap cho hầu hết kích thước input.

Lazy deletion trade-off: Heap có thể chứa tối đa $O(E)$ entry (mỗi relaxation push 1 entry). Mỗi heappop tốn $O(\log E)=O(\log V)$ (vì $E\le V^2$). Tổng: $O(E\log V)$ — cùng complexity nhưng constant factor nhỏ hơn decrease-key approach.

Dense vs sparse graph: Khi $E\approx V^2$ (dense), $O((V+E)\log V)=O(V^2\log V)$ — chậm hơn approach dùng mảng $O(V^2)$. Trong production, hầu hết graph là sparse nên binary heap thắng.

Trade-offs

Tiêu chí	Dijkstra	BFS	Bellman-Ford
Trọng số	≥ 0	Không trọng số	Bất kỳ (kể cả âm)
Time	$O((V+E)\log V)$	$O(V+E)$	$O(V\times E)$
Phát hiện chu trình âm	❌	❌	✅
Phù hợp	GPS, OSPF, game	Web crawler, social network	Forex arbitrage, BGP

Checklist ghi nhớ

✅ Checklist triển khai

Trước khi code

• [ ] Xác nhận trọng số đồ thị ≥ 0 (nếu có âm → dùng Bellman-Ford)
• [ ] Xác định cần single-source hay all-pairs (all-pairs → xét Floyd-Warshall)
• [ ] Đồ thị sparse hay dense (dense + V nhỏ → dùng mảng $O(V^2)$)

Khi code Dijkstra

• [ ] Khởi tạo dist[src] = 0, dist[i] = INF cho mọi i ≠ src
• [ ] Dùng min-heap (C++: greater<pii>, Java: Comparator.comparingInt)
• [ ] Kiểm tra lazy deletion: if d > dist[u]: continue
• [ ] Push (dist[v], v) vào heap khi relaxation thành công

Tối ưu production

• [ ] Early termination nếu chỉ cần đường đến 1 đích cụ thể
• [ ] Truy vết đường đi bằng mảng prev[] nếu cần path reconstruction
• [ ] Cân nhắc A* (Dijkstra + heuristic) nếu có thông tin bổ sung về đích

Bài tập luyện tập

Bài 1: Shortest Path cơ bản — Foundation

Đề bài: Cho đồ thị có hướng, có trọng số không âm, gồm V đỉnh và E cạnh. Tìm khoảng cách ngắn nhất từ đỉnh 0 đến tất cả các đỉnh khác.

Input: V=5, E=6
Edges: (0,1,2), (0,2,4), (1,2,1), (1,3,7), (2,4,3), (3,4,1)

Output: [0, 2, 3, 9, 6]

🧠 Quiz

Câu hỏi: Sau khi pop đỉnh u từ min-heap, điều gì chắc chắn đúng về dist[u]?

• [ ] A. dist[u] là khoảng cách ngắn nhất nếu đồ thị không có chu trình
• [x] B. dist[u] là khoảng cách ngắn nhất từ nguồn đến u (với trọng số ≥ 0)
• [ ] C. dist[u] có thể được cập nhật thêm bởi các đỉnh chưa xử lý
• [ ] D. dist[u] chỉ chính xác nếu u nằm trên đường đi ngắn nhất đến đích cuối Giải thích: Đây là bất biến cốt lõi của Dijkstra. Khi pop đỉnh có khoảng cách nhỏ nhất từ heap, không thể tồn tại đường nào ngắn hơn qua các đỉnh chưa xử lý (vì tất cả trọng số ≥ 0). Option C sai vì Dijkstra greedy-lock khoảng cách.

💡 Gợi ý

• Xây adjacency list, khởi tạo dist, push source vào min-heap
• Lặp: pop min, skip stale, relax neighbors

✅ Lời giải

import heapq

def solve(V: int, edges: list[tuple[int, int, int]]) -> list[int]:
    adj = [[] for _ in range(V)]
    for u, v, w in edges:
        adj[u].append((v, w))

    dist = [float('inf')] * V
    dist[0] = 0
    pq = [(0, 0)]

    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue
        for v, w in adj[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush(pq, (dist[v], v))

    return dist

Phân tích: Time $O((V+E)\log V)$, Space $O(V+E)$.

Bài 2: K-th Shortest Path — Intermediate

Đề bài: Tìm đường đi ngắn thứ K từ đỉnh src đến đỉnh dst. Cho phép đi qua cùng đỉnh nhiều lần.

💡 Gợi ý

• Sửa Dijkstra: cho phép pop cùng đỉnh tối đa K lần
• Lần thứ K pop đỉnh dst chính là đáp án

✅ Lời giải

import heapq

def kth_shortest(V: int, adj: list[list[tuple[int, int]]],
                 src: int, dst: int, k: int) -> int:
    count = [0] * V
    pq = [(0, src)]

    while pq:
        d, u = heapq.heappop(pq)
        count[u] += 1

        if u == dst and count[u] == k:
            return d

        if count[u] > k:
            continue

        for v, w in adj[u]:
            heapq.heappush(pq, (d + w, v))

    return -1  # Không tồn tại K đường đi

Phân tích: Time $O(K\times E\log (K\times V))$, Space $O(K\times V)$. Lưu ý: không dùng lazy deletion ở đây vì cần cho phép pop cùng đỉnh nhiều lần.

Liên kết học tiếp

📚 Bài liên quan

Bài liên quan trong Penalgo

• ← BFS & DFS — Nền tảng duyệt đồ thị
• → Bellman-Ford — Shortest path hỗ trợ trọng số âm
• Floyd-Warshall — All-pairs shortest path
• MST — Prim & Kruskal — Cây khung nhỏ nhất, cũng dùng greedy + heap

Từ khóa glossary: Dijkstra, shortest path, đường đi ngắn nhất, priority queue, min-heap, relaxation, greedy algorithm

Tìm kiếm liên quan: thuật toán Dijkstra, tìm đường ngắn nhất, shortest path algorithm, GPS routing