Chuyển tới nội dung chính

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

Bạn sẽ học được gì

Dijkstra tìm đường đi ngắn nhất từ một nguồn tới mọi đỉnh khác, khi các cạnh có trọng số không âm. BFS đếm số cạnh; Dijkstra cộng trọng số. Bí quyết tốc độ là một hàng đợi ưu tiên / heap luôn cho ra đỉnh gần nhất chưa chốt, đạt O(E log V).

1. Trực quan: luôn mở rộng đỉnh rẻ nhất​

Hãy hình dung bạn đi từ nhà tới mọi địa điểm, mỗi đoạn đường tốn một số phút. Dijkstra theo nguyên tắc tham lam: trong số những nơi chưa chốt, luôn bước tới nơi có tổng thời gian nhỏ nhất trước. Vì cạnh không âm, một khi đã chốt một đỉnh thì khoảng cách của nó không thể tốt hơn nữa.

        2        3
   A ------- B ------- D
    \                 /
     \ 6           1 /
      \             /
        ---- C -----
   Tu A:
   dist[A]=0
   dist[B]=2   (A->B)
   dist[C]=6   (A->C)
   dist[D]=5   (A->B->D = 2+3)  re hon A->C->D = 6+1=7

2. Cơ chế: heap + bảng dist​

Thành phầnVai trò
dist[v]khoảng cách ngắn nhất đã biết tới v (khởi tạo vô cực)
heapcặp (khoang_cach, dinh), luôn lấy ra đỉnh nhỏ nhất
giãn cạnh (relax)nếu dist[v] > dist[u] + w thì cập nhật dist[v]

Vòng lặp: lấy đỉnh u rẻ nhất ra khỏi heap, thử giãn mọi cạnh đi ra của nó. Nếu tìm được đường tốt hơn tới hàng xóm v, cập nhật và đẩy (dist_moi, v) vào heap.

Vì sao Dijkstra cần cạnh KHÔNG ÂM?

Tính tham lam dựa trên giả định: đã lấy đỉnh nhỏ nhất ra thì không gì làm nó nhỏ hơn được nữa. Cạnh âm phá vỡ điều này — lúc đó phải dùng Bellman-Ford.

3. Chạy debug: Dijkstra từng bước​

🐞 Dijkstra từ ABước 1/8
1import heapq
2g = {"A":[("B",2),("C",6)], "B":[("D",3)], "C":[("D",1)], "D":[]}
3dist = {"A":0}
4pq = [(0, "A")]
5while pq:
6  d, u = heapq.heappop(pq)
7  for v, w in g[u]:
8      if d + w < dist.get(v, 1e9):
9          dist[v] = d + w
10          heapq.heappush(pq, (dist[v], v))
Biến tại bước này
distA:0
pq[(0,A)]
👉 Nguồn A khoảng cách 0.

4. Code chạy được​

Đang tải trình chạy code…
Bỏ qua bản ghi cũ

Một đỉnh có thể bị đẩy vào heap nhiều lần với các khoảng cách khác nhau. Dòng if d > dist[u]: continue bỏ qua bản ghi đã lỗi thời, giúp thuật toán đúng và hiệu quả mà không cần xoá khỏi heap.

5. Phân tích​

Khía cạnhGiá trị
Thời gianO(E log V) với binary heap
Bộ nhớO(V + E)
Điều kiệnTrọng số không âm

Bẫy thường gặp:

  • Có cạnh âm → Dijkstra cho kết quả sai. Dùng Bellman-Ford.
  • Quên kiểm tra bản ghi cũ → vẫn đúng nhưng làm nhiều việc thừa.
  • So sánh sai: phải cập nhật khi dist[v] > dist[u] + w.

6. Mẫu nhận diện​

  • "Đường đi ngắn nhất" + "cạnh có trọng số không âm" → Dijkstra.
  • "Chi phí / thời gian / khoảng cách nhỏ nhất từ một điểm" → Dijkstra một nguồn.
  • Bản đồ định tuyến, mạng, trò chơi có chi phí di chuyển khác nhau → Dijkstra.

7. 🎮 Trò chơi: Hiểu Dijkstra​

🎮 Hiểu DijkstraCâu 1/4· Điểm 0· 🔥 0

Dijkstra tham lam: luôn mở rộng đỉnh rẻ nhất chưa chốt. Chỉ đúng khi cạnh không âm.

Khoảng cách ngắn nhất từ A tới D?

A->B = 2, B->D = 3, A->C = 6, C->D = 1
# dist[D] ngan nhat tu A = ?

8. Quiz kiểm tra nhanh​

📝 Quiz kiểm tra nhanh
1. Độ phức tạp của Dijkstra dùng binary heap là?
2. Khác biệt cốt lõi giữa BFS và Dijkstra là?
3. Nếu đồ thị có cạnh trọng số âm thì nên dùng?

9. Hoàn thành​

…

☑️ Tiếp theo: 3.3.5 — Bellman-Ford & Floyd-Warshall (xử lý cạnh âm và mọi cặp đỉnh).