Dijkstra — Shortest path trên weighted graph với PriorityQueue

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, PriorityQueue 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. Vertex 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" vertex 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] = best known shortest distance từ start đến v. Ban đầu:

• dist[start] = 0
• dist[v] = Integer.MAX_VALUE (vô cùng) cho mọi v khác

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

if dist[u] + w < dist[v]:
    dist[v] = dist[u] + w  // cap nhat duong ngan hon
    push (v, dist[v]) vao PQ

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 poll vertex u có dist[u] nhỏ nhất từ PQ — 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 vertex khác w chưa finalized. Nhưng dist[w] >= dist[u] (ta đang poll min) → 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 — JDK PriorityQueue

JDK PriorityQueue không support 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 PQ — entry cũ vẫn còn.
• Khi poll entry (u, d): nếu d > dist[u], entry này là outdated (dist đã được update về giá trị tốt hơn trước đó) → skip.

if (curr.dist() > dist[u]) continue;  // outdated entry -- skip

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

3. Code Java đầy đủ

import java.util.*;

public class Dijkstra {
    record Edge(int to, int weight) {}
    record State(int vertex, int dist) {}

    // Returns dist[] from start to every vertex.
    // dist[v] = Integer.MAX_VALUE means unreachable.
    public static int[] dijkstra(List<List<Edge>> adj, int start) {
        int n = adj.size();
        int[] dist = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[start] = 0;

        PriorityQueue<State> pq =
            new PriorityQueue<>(Comparator.comparingInt(State::dist));
        pq.offer(new State(start, 0));

        while (!pq.isEmpty()) {
            State curr = pq.poll();
            int u = curr.vertex();

            // Lazy deletion: skip outdated entry
            if (curr.dist() > dist[u]) continue;

            for (Edge e : adj.get(u)) {
                // Guard against Integer.MAX_VALUE overflow
                if (dist[u] == Integer.MAX_VALUE) continue;

                int newDist = dist[u] + e.weight();
                if (newDist < dist[e.to()]) {
                    dist[e.to()] = newDist;
                    pq.offer(new State(e.to(), newDist));
                }
            }
        }
        return dist;
    }
}

3.1 Trace ví dụ — graph 5 vertex

Graph directed weighted:

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

Edges: 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ế.

public static List<Integer> shortestPath(List<List<Edge>> adj,
                                          int start, int target) {
    int n = adj.size();
    int[] dist = new int[n];
    int[] parent = new int[n];
    Arrays.fill(dist, Integer.MAX_VALUE);
    Arrays.fill(parent, -1);
    dist[start] = 0;

    PriorityQueue<State> pq =
        new PriorityQueue<>(Comparator.comparingInt(State::dist));
    pq.offer(new State(start, 0));

    while (!pq.isEmpty()) {
        State curr = pq.poll();
        int u = curr.vertex();
        if (curr.dist() > dist[u]) continue;

        for (Edge e : adj.get(u)) {
            if (dist[u] == Integer.MAX_VALUE) continue;
            int newDist = dist[u] + e.weight();
            if (newDist < dist[e.to()]) {
                dist[e.to()] = newDist;
                parent[e.to()] = u;          // track how we reached e.to()
                pq.offer(new State(e.to(), newDist));
            }
        }
    }

    if (dist[target] == Integer.MAX_VALUE) return List.of(); // unreachable

    // Reconstruct path from target back to start
    List<Integer> path = new ArrayList<>();
    for (int cur = target; cur != -1; cur = parent[cur]) {
        path.add(cur);
    }
    Collections.reverse(path);
    return path;
}

Vì sao reverse? Ta đi ngược từ target về start qua parent[]. Kết quả thu được là path ngược — reverse để có thứ tự từ start đến target.

5. Complexity

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

• Mỗi vertex được poll tối đa một lần: V lần poll, mỗi lần log(PQ size) ≈ log V → V log V.
• Mỗi edge có thể trigger một push vào PQ: 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 PQ — mỗi lần tìm vertex 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 finalize vertex u, dist[u] là final. Nhưng với edge âm, vertex đã finalized có thể được cải thiện thêm — invariant sai.

Counter-example:

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

Edges: A→B weight 5, A→C weight 4, C→B weight -3.

Dijkstra: dist = [0, ∞, ∞]. Poll A (dist 0) → relax B=5, C=4. PQ: [(C,4),(B,5)]. Poll C (dist 4) → relax B via C: 4 + (-3) = 1 < 5 → dist[B] = 1, push (B,1). PQ: [(B,1),(B,5)]. Poll B (dist 1) → finalized.

Kết quả đúng lần này vì counter-example này thực ra Dijkstra handle được (vì C được expand trước B). Nhưng xét:

A ---(2)---> B
|            |
(4)        (−10)
|            v
+-----> C    D

A→B w2, A→C w4, B→D w-10. Dijkstra poll A → B=2, C=4. Poll B (dist 2) → D = 2+(-10) = -8. Poll C (dist 4) → không relax D. Kết quả D = -8. Đúng!

Vấn đề xảy ra khi edge âm dẫn đến vertex đã finalized:

A ---(1)---> B ---(−5)---> C
|
+(2)
|
v
C

A→B w1, A→C w2, B→C w-5. Dijkstra: poll A → B=1, C=2. Poll B → C = 1+(-5) = -4. Nhưng C đã được relax thành 2 — nếu C chưa poll khỏi PQ thì OK (dist[C] sẽ update -4). Nếu implementation poll C trước khi relax từ B → finalize C=2, sau đó poll B mới phát hiện C có thể là -4 nhưng C đã finalized → 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: "chi co negative cycle moi sai, negative edge thuong thi OK"
// Dijkstra sai ngay ca khi chi co 1 negative edge, khong co cycle
// Test case: A->B w1, A->C w3, C->B w(-3) -- Dijkstra cho dist[B]=1, correct la -0 (=A->C->B = 0)
// Thuc ra 3+(-3)=0 < 1 nhung Dijkstra finalize B=1 truoc khi expand C

Test kỹ trước khi chọn Dijkstra: nếu bất kỳ edge nào có weight âm, dùng Bellman-Ford.

Pitfall 2 — Quên lazy skip pattern

// BUG: push duplicate vao PQ nhung khong skip outdated
while (!pq.isEmpty()) {
    State curr = pq.poll();
    int u = curr.vertex();
    // MISSING: if (curr.dist() > dist[u]) continue;

    for (Edge e : adj.get(u)) {
        int newDist = dist[u] + e.weight();
        if (newDist < dist[e.to()]) {
            dist[e.to()] = newDist;
            pq.offer(new State(e.to(), newDist));
            // Now dist[e.to()] updated, but old entry still in PQ
            // Without skip, old entry will re-relax neighbors with stale dist
        }
    }
}
// Result may still be correct on many inputs, but slower and can be wrong
// on certain graph topologies -- subtle bug hard to reproduce

Luôn có dòng if (curr.dist() > dist[u]) continue; ngay sau pq.poll().

Pitfall 3 — Integer.MAX_VALUE overflow trong addition

// BUG: dist[u] = Integer.MAX_VALUE, e.weight() = 5
// Integer.MAX_VALUE + 5 overflows to negative number
int newDist = dist[u] + e.weight();  // overflow -> negative -> wrong comparison
if (newDist < dist[e.to()]) { ... }  // always true -> corrupts dist array

// CORRECT: guard before addition
if (dist[u] == Integer.MAX_VALUE) continue;
int newDist = dist[u] + e.weight();

Hoặc dùng 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. PQ 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" vertex ít quan trọng, tạo shortcut edge. Query time dưới 10ms cho graph 1 triệu vertex. 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...).

Indexed PQ: support decrease-key thực sự thay vì lazy deletion. Code phức tạp hơn đáng kể, benefit biên trong practice. Fibonacci heap có asymptotic tốt hơn nhưng constant lớn.

9. Quy mô lớn — graph 1 triệu vertex

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

• PQ 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 vertex). 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 — vertex 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 vertex có dist nhỏ nhất chưa finalized — greedy invariant đúng khi mọi edge weight không âm.
• Relaxation: với edge u → v weight w, nếu dist[u] + w < dist[v] thì update dist[v] và push entry mới vào PQ.
• Lazy deletion pattern: JDK PriorityQueue không có decrease-key — push duplicate, skip outdated với if (curr.dist() > dist[u]) continue.
• Complexity O((V+E) log V): mỗi vertex poll một lần V log V, mỗi edge có thể trigger push E log V.
• FAIL với negative edge: greedy invariant sai — vertex đã 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, sau đó reverse.
• 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