Dijkstra — Shortest path trên weighted graph với min-heap

TL;DR: Dijkstra tìm shortest path trên weighted graph (mọi cạnh có weight không âm) bằng cách luôn mở rộng đỉnh có tổng cost nhỏ nhất chưa finalized — một quyết định tham lam (greedy) đúng đắn nhờ không có cạnh âm. Cấu trúc dữ liệu cốt lõi là min-heap (priority queue); mỗi lần cải thiện dist của đỉnh v, push entry mới vào heap và bỏ qua entry cũ khi pop (lazy deletion). Complexity O((V+E) log V). Pitfall lớn nhất: Dijkstra FAIL khi có bất kỳ cạnh âm nào — kể cả không có negative cycle — vì greedy invariant bị phá vỡ; dùng Bellman-Ford thay thế.

Bạn đã biết BFS tìm shortest path trên unweighted graph (lesson 02) — mỗi cạnh có weight bằng 1, BFS đảm bảo path ít cạnh nhất. Nhưng Google Maps không đếm số ngã tư — nó tính thời gian di chuyển. Đường cao tốc từ Hà Nội đến Bắc Ninh có thể nhanh hơn đường làng dù nhiều "ngã rẽ" hơn. Mỗi cạnh trong road network có weight riêng: travel time, distance, hoặc cost.

BFS trên weighted graph cho kết quả sai hoàn toàn — nó tối ưu theo số cạnh, không theo tổng weight. Cần một algorithm khác.

Bài này dạy Dijkstra: relaxation principle, min-heap implementation O((V+E) log V), vì sao FAIL với edge âm, và pattern Google Maps / OSPF routing dùng.

1. Analogy — Lan tỏa wave với tốc độ khác nhau

BFS giống sóng nước trên mặt hồ phẳng — sóng lan đều mọi hướng, mỗi "bước" là một cạnh có cost bằng nhau.

Dijkstra giống sóng lan trên địa hình gồ ghề: đường rộng (weight nhỏ) sóng lan nhanh hơn, đường núi (weight lớn) sóng lan chậm hơn. Đỉnh nào bị sóng chạm trước thì tổng cost từ source đến đó là nhỏ nhất.

Greedy core: tại mỗi bước, Dijkstra luôn "expand" đỉnh gần source nhất (theo tổng cost) chưa được finalize — đây là quyết định locally optimal, và với graph không có edge âm, nó cho kết quả globally optimal.

2. Thuật toán — Relaxation principle

2.1 Distance estimate và relaxation

dist[v] là ước tính tốt nhất hiện tại về shortest distance từ start đến v. Ban đầu:

• dist[start] = 0
• dist[v] = INF cho mọi v khác

Relaxation: với mỗi cạnh u → v có weight w, kiểm tra:

if dist[u] + w < dist[v]:
    dist[v] <- dist[u] + w    -- cập nhật đường ngắn hơn
    push (v, dist[v]) vào MinHeap

Tên "relaxation" từ ý tưởng: ta đang "nới lỏng" ước tính dist của v xuống giá trị tốt hơn.

2.2 Greedy invariant

Khi pop đỉnh u có dist[u] nhỏ nhất từ MinHeap — dist[u] là final shortest distance từ start đến u.

Proof intuition: giả sử tồn tại path ngắn hơn đến u. Path đó phải đi qua một đỉnh khác w chưa finalized. Nhưng dist[w] >= dist[u] (ta đang pop min) nên path đó có tổng cost ít nhất là dist[w] >= dist[u] — mâu thuẫn với "ngắn hơn". Điều này chỉ đúng khi tất cả edge weight không âm.

2.3 Lazy deletion pattern

Nhiều ngôn ngữ (Java, Python) không cung cấp min-heap có decrease-key trực tiếp. Thay vào đó dùng lazy deletion:

• Khi dist của v được cải thiện, push entry mới (v, newDist) vào heap — entry cũ vẫn còn.
• Khi pop entry (u, d): nếu d > dist[u], entry này là outdated (dist đã được update về giá trị tốt hơn) → skip.

if d > dist[u]: continue   -- entry cũ (lazy deletion), bỏ qua

Lazy deletion đơn giản hơn nhiều so với indexed heap nhưng heap có thể chứa O(E) entries thay O(V). Với sparse graph (E ≈ V log V), không đáng kể.

3. Pseudocode đầy đủ

Dijkstra(G, start):
    dist[v] <- INF cho mọi v
    dist[start] <- 0
    parent[v] <- NIL cho mọi v

    H <- MinHeap rỗng        -- keyed by dist
    H.push((start, 0))

    while H không rỗng:
        (u, d) <- H.pop()    -- lấy đỉnh có dist nhỏ nhất

        if d > dist[u]: continue   -- entry cũ (lazy deletion), bỏ qua

        for each cạnh (u -> v, trọng số w) trong G:
            newDist <- dist[u] + w
            if newDist < dist[v]:
                dist[v] <- newDist
                parent[v] <- u
                H.push((v, newDist))

    return dist, parent
    -- dist[v] = INF nếu v không thể tới từ start

Time: O((V+E) log V) Space: O(V+E)

flowchart TD
    INIT["dist[start]=0, đẩy (start,0) vào heap"]
    POP["Lấy (u, d) từ MinHeap"]
    SKIP{"d > dist[u]?"}
    RELAX["Relax mỗi cạnh u->v:\nnewDist = dist[u] + w\nnếu ngắn hơn: cập nhật dist[v], đẩy (v,newDist)"]
    DONE["Trả về dist[], parent[]"]

    INIT --> POP
    POP --> SKIP
    SKIP -- "có (entry cũ)" --> POP
    SKIP -- "không" --> RELAX
    RELAX --> POP
    POP -- "heap rỗng" --> DONE

3.1 Trace ví dụ — graph 5 đỉnh

Graph directed weighted:

    (2)      (3)
0 ----> 1 ----> 3
|       |       ^
|(4)   (1)     |(1)
v       v      |
2 ----> 4 -----+
    (2)    (1)

Cạnh: 0→1 w2, 0→2 w4, 1→3 w3, 1→4 w1, 2→4 w2, 4→3 w1.

Kết quả: dist = [0, 2, 4, 4, 3]. Shortest path từ 0 đến 3: cost 4 qua 0→1→4→3.

4. Path reconstruction

Theo dõi thêm mảng parent[] trong quá trình relaxation để reconstruct path thực tế.

reconstruct_path(parent, start, target):
    if dist[target] = INF: return []   -- không thể tới

    path <- []
    cur <- target
    while cur != NIL:
        path.prepend(cur)
        cur <- parent[cur]
    return path   -- thứ tự từ start đến target

Time: O(V) Space: O(V)

Vì sao prepend (hoặc reverse)? Ta đi ngược từ target về start qua chuỗi parent[]. Nếu dùng append và reverse, kết quả giống nhau. Nếu dùng prepend (insert đầu), list đã đúng thứ tự.

5. Complexity

Binary heap O((V+E) log V) từ đâu?

• Mỗi đỉnh được pop tối đa một lần: V lần pop, mỗi lần log(heap size) ≈ log V → V log V.
• Mỗi cạnh có thể trigger một push vào heap: E lần push, mỗi lần log V → E log V.
• Tổng: O(V log V + E log V) = O((V + E) log V).

Array-based O(V²): không dùng heap — mỗi lần tìm đỉnh unvisited có dist nhỏ nhất bằng linear scan O(V), lặp V lần → O(V²). Với dense graph E = O(V²), array-based thắng vì không overhead heap.

6. Vì sao FAIL với negative edge

6.1 Greedy assumption bị phá vỡ

Dijkstra dựa trên invariant: khi pop đỉnh u (vì dist[u] nhỏ nhất trong heap), dist[u] đã là final — không edge nào sau đó cải thiện được nữa. Invariant này chỉ đúng khi mọi edge không âm: thêm một cạnh chỉ tăng hoặc giữ nguyên cost. Một cạnh âm phá vỡ giả định này — một path "dài hơn" tới u (nhiều cạnh hơn) vẫn có thể rẻ hơn nhờ cạnh âm.

Counter-example (một ví dụ đủ để thấy sai):

        (1)
   A ---------> B
   |            ^
  (3)         (-5)
   |            |
   +----> C ----+

Cạnh: A→B weight 1, A→C weight 3, C→B weight -5. Shortest path thực tới B là A→C→B = 3 + (-5) = -2, không phải đường trực tiếp A→B = 1.

Dijkstra (finalize khi pop): dist = [0, INF, INF]. Pop A (0) → relax B=1, C=3. Heap: [(B,1),(C,3)]. Pop B (dist 1, nhỏ hơn C) → finalize B=1. Pop C (3) → relax B: 3 + (-5) = -2 < 1 — nhưng B đã finalized → bỏ qua. Kết quả báo dist[B] = 1, trong khi đáp án đúng là -2. Sai.

Gốc rễ: Dijkstra finalize B trước khi khám phá đường vòng qua C, vì greedy tin "đã nhỏ nhất thì không thể nhỏ hơn". Với cạnh âm, niềm tin đó sai.

6.2 Negative cycle — không có shortest path

Nếu graph có negative cycle (cycle với tổng weight âm), không tồn tại shortest path — ta có thể đi vòng quanh cycle vô hạn lần, giảm total cost mãi.

Dijkstra không detect được negative cycle (sẽ loop hoặc cho kết quả sai). Dùng Bellman-Ford (lesson 06) để handle cả negative edge và detect negative cycle.

7. Pitfall tổng hợp

Pitfall 1 — Nhầm "negative weight" với "negative cycle"

-- BUG assumption: "chỉ có negative cycle mới sai, negative edge thường thì OK"
-- Dijkstra sai ngay cả khi chỉ có 1 negative edge, không có cycle
-- Test case: A->B w1, A->C w3, C->B w(-3)
-- Dijkstra cho dist[B]=1, correct là A->C->B = 3+(-3)=0
-- Nhưng 0 < 1 mà Dijkstra finalize B=1 trước khi expand C
-- => Phải dùng Bellman-Ford

Pitfall 2 — Quên lazy skip pattern

-- BUG: push duplicate vào heap nhưng không skip entry cũ
while H không rỗng:
    (u, d) <- H.pop()
    -- THIẾU: if d > dist[u]: continue

    for each cạnh (u -> v, w):
        newDist <- dist[u] + w
        if newDist < dist[v]:
            dist[v] <- newDist
            H.push((v, newDist))
            -- entry cũ (v, oldDist) vẫn còn trong heap
            -- không skip -> sẽ re-relax neighbor với dist cũ
            -- tốn thêm thời gian do re-relax entry cũ
            -- (kết quả vẫn đúng nếu relax dùng dist[u] từ mảng,
            --  chỉ sai nếu implementation relax bằng d của entry
            --  thay vì dist[u] từ mảng)

Luôn có dòng if d > dist[u]: continue ngay sau H.pop(). Thiếu dòng này không nhất thiết cho kết quả sai (nếu relax dùng dist[u] từ mảng), nhưng gây re-relax không cần thiết, tốn thêm thời gian — và dễ dẫn đến lỗi nếu implementation vô tình dùng d thay vì dist[u] khi relax.

Pitfall 3 — Overflow khi cộng INF với weight

-- BUG: dist[u] = INF (giả sử là MAX_INT), w = 5
-- MAX_INT + 5 tràn số (overflow) -> số âm -> sai hoàn toàn
newDist <- dist[u] + w   -- overflow -> negative -> wrong comparison
if newDist < dist[v]: ...   -- luôn true -> làm hỏng dist array

-- CORRECT: guard trước khi cộng
if dist[u] = INF: continue   -- không thể đi tới u, bỏ qua
newDist <- dist[u] + w

Hoặc dùng kiểu số 64-bit (long) cho dist[] và weight, tránh overflow hoàn toàn.

8. Variants và optimizations

A* (A-star): Dijkstra cộng thêm heuristic h(v) ước tính distance từ v đến goal. Heap key = dist[v] + h(v). Nếu h là admissible (không overestimate) — ví dụ Euclidean distance trên grid — A* tìm optimal path nhanh hơn Dijkstra vì ưu tiên expand theo hướng goal. Dùng trong game pathfinding (NPC), routing có endpoint rõ ràng.

Bidirectional Dijkstra: chạy Dijkstra từ start tiến về phía trước và từ goal tiến ngược lại. Dừng khi hai frontier gặp nhau. Chi phí giảm từ O(b^d) xuống O(b^(d/2)), trong đó b là branching factor. Đây là technique Google Maps dùng cho large road network.

Contraction Hierarchy: pre-process graph bằng cách "contract" đỉnh ít quan trọng, tạo shortcut edge. Query time dưới 10ms cho graph 1 triệu đỉnh. Production standard cho realtime routing.

k-shortest paths (Yen's algorithm): tìm K path ngắn nhất, không chỉ một. Dùng khi muốn backup routes (nếu đường 1 tắc, dùng đường 2, 3...).

9. Quy mô lớn — graph 1 triệu đỉnh

Dijkstra full V × log V operations trong heap. Với V = 1 triệu, E = 5 triệu:

• Heap operations: (V + E) × log V ≈ 6M × 20 = 120 triệu operations.
• Mỗi operation khoảng 100ns → khoảng 12 giây. Quá lâu cho realtime routing.

Production solution: pre-compute với Contraction Hierarchy + bidirectional Dijkstra. Query time dưới 10ms cho full road network châu Âu (hàng chục triệu đỉnh). Google Maps, HERE Maps, OpenStreetMap Valhalla đều dùng approach này.

Offline batch routing (tìm shortest path cho 1000 request/s không cần realtime): Dijkstra naive đủ nếu scale ngang (nhiều worker xử lý song song).

10. Ứng dụng thực tế

Google Maps / OpenStreetMap routing: Dijkstra với edge weight = travel time (tính từ speed limit × distance). Bidirectional Dijkstra + Contraction Hierarchy cho realtime. A* với Euclidean heuristic cho grid-based map. Edge weight thay đổi theo giờ (giờ cao điểm) → time-dependent Dijkstra với edge weight là function của thời gian.

OSPF (Open Shortest Path First) — Internet routing: mỗi router chạy Dijkstra trên link-state database (graph topology toàn mạng) để tính shortest path tree từ nó đến mọi router khác. Edge weight = link cost (bandwidth, latency). Khi topology thay đổi (router down, link cost change), router cập nhật database và re-run Dijkstra. Đây là lý do OSPF có tên "Shortest Path First" — Dijkstra là core algorithm.

Game AI pathfinding: A* (Dijkstra + heuristic) cho NPC tìm đường trên grid map. Edge weight = terrain cost (đường, rừng, nước có cost khác nhau). Bidirectional A* cho map lớn (open-world game). Dijkstra baseline trước khi thêm heuristic.

Public transit routing (Citymapper, Google Transit): Dijkstra với edge weight = travel time + transfer penalty. Graph phức tạp hơn road network — đỉnh là (station, time) combination (time-expanded graph). Dijkstra trên time-expanded graph tìm fastest itinerary kể cả transfer time và departure schedule.

Telegram / messaging delivery path: trong distributed system, tìm shortest hop từ sender đến recipient qua network topology. Edge weight = latency. Dijkstra trên network graph cho routing table tối ưu.

11. Deep Dive

12. Tóm tắt

• Dijkstra tìm shortest path trên weighted graph bằng cách luôn expand đỉnh có dist nhỏ nhất chưa finalized — greedy invariant đúng khi mọi edge weight không âm.
• Relaxation: với cạnh u → v weight w, nếu dist[u] + w < dist[v] thì update dist[v] và push entry mới vào heap.
• Lazy deletion pattern: heap thường không có decrease-key — push duplicate, skip outdated với if d > dist[u]: continue.
• Complexity O((V+E) log V): mỗi đỉnh pop một lần V log V, mỗi cạnh có thể trigger push E log V.
• FAIL với negative edge: greedy invariant sai — đỉnh đã finalized có thể bị cải thiện bởi edge âm. Dùng Bellman-Ford khi có edge âm.
• Path reconstruction qua parent[] array — đi ngược từ target về start.
• Variants: A* thêm heuristic cho goal-directed search, Bidirectional Dijkstra giảm search space, Contraction Hierarchy cho production realtime routing.
• Ứng dụng: Google Maps routing, OSPF Internet routing, game AI pathfinding, public transit planning.

13. Tự kiểm tra

Bài tiếp theo: Bellman-Ford — handle negative weight