Bài 2: Pathfinding Dijkstra & A* — Tìm Đường Ngắn Nhất

Ở Bài 1 chúng ta đã trực quan hoá cây tự cân bằng. Bài này chuyển sang một bài toán kinh điển khác của khoa học máy tính: tìm đường đi ngắn nhất trên đồ thị có trọng số — nền tảng của mọi ứng dụng bản đồ, định tuyến mạng, và AI tìm đường trong game.

1. Vì sao BFS không đủ khi đồ thị có trọng số?

Duyệt theo chiều rộng (Breadth-First Search — BFS) tìm đường đi ngắn nhất theo số cạnh — hoạt động hoàn hảo khi mọi cạnh có "chi phí" bằng nhau. Nhưng trong thực tế, các cạnh thường có trọng số khác nhau (khoảng cách, thời gian di chuyển, chi phí băng thông). BFS không phân biệt được đường đi 1 cạnh nặng với đường đi 3 cạnh nhẹ.

// Biểu diễn đồ thị có trọng số bằng danh sách kề (adjacency list)
const graph = {
  A: [{ to: 'B', weight: 4 }, { to: 'C', weight: 1 }],
  B: [{ to: 'D', weight: 1 }],
  C: [{ to: 'B', weight: 1 }, { to: 'D', weight: 5 }],
  D: [],
};
// BFS từ A tới D sẽ chọn A -> B -> D (2 cạnh) vì "ngắn hơn" về SỐ BƯỚC
// nhưng tổng trọng số thực tế là 4 + 1 = 5
// Trong khi A -> C -> B -> D chỉ tốn 1 + 1 + 1 = 3 (ít hơn!) dù đi 3 cạnh
// => Cần thuật toán biết CỘNG DỒN trọng số, không chỉ đếm cạnh

2. Giải thuật Dijkstra: Relaxation & Priority Queue

Edsger Dijkstra (1959) giải bài toán trên bằng cách luôn mở rộng node có tổng khoảng cách nhỏ nhất đã biết trước. Ý tưởng cốt lõi là phép relaxation (nới lỏng): với mỗi cạnh (u, v, w), nếu đi qua u tới v ngắn hơn đường hiện đã biết tới v, cập nhật lại khoảng cách của v.

function dijkstra(graph, start, end) {
  const dist = { [start]: 0 };
  const prev = {};
  // Priority queue thực tế nên dùng binary heap O((V+E) log V);
  // ở đây minh hoạ bằng mảng + tìm min tuyến tính cho dễ hiểu
  const queue = [{ node: start, dist: 0 }];
  const visited = new Set();

  while (queue.length > 0) {
    queue.sort((a, b) => a.dist - b.dist);
    const { node: u } = queue.shift();
    if (visited.has(u)) continue;
    visited.add(u);
    if (u === end) break;

    for (const { to: v, weight: w } of graph[u] || []) {
      const newDist = dist[u] + w;
      // Bước RELAXATION: tìm thấy đường ngắn hơn thì cập nhật
      if (dist[v] === undefined || newDist < dist[v]) {
        dist[v] = newDist;
        prev[v] = u;
        queue.push({ node: v, dist: newDist });
      }
    }
  }
  return { dist, prev };
}

Điểm mấu chốt: vì luôn xử lý node gần nhất trước, khi node đích được lấy ra khỏi hàng đợi, khoảng cách của nó chắc chắn đã tối ưu — không cần xét lại. Đây là lý do Dijkstra đảm bảo kết quả đúng cho mọi đồ thị trọng số không âm.

3. Giải thuật A*: Heuristic dẫn đường đi nhanh hơn

Dijkstra "mù" — nó mở rộng đều theo mọi hướng cho tới khi chạm đích, kể cả những hướng rõ ràng đi xa đích. A* (Hart, Nilsson, Raphael — 1968) cải tiến bằng cách cộng thêm một hàm heuristic ước lượng khoảng cách còn lại tới đích, giúp thuật toán "có định hướng" hơn:

Trong đó $g(n)$ là chi phí thực tế đã đi từ điểm bắt đầu tới node $n$ (giống Dijkstra), còn $h(n)$ là ước lượng chi phí còn lại từ $n$ tới đích. A* luôn mở rộng node có $f(n)$ nhỏ nhất — vừa xét đường đã đi, vừa xét hướng có vẻ gần đích.

Hai hàm heuristic phổ biến nhất cho lưới ô vuông (grid) di chuyển 4 hướng:

// Manhattan: đúng khi chỉ di chuyển 4 hướng (lên/xuống/trái/phải)
function manhattan(a, b) {
  return Math.abs(a.x - b.x) + Math.abs(a.y - b.y);
}

// Euclidean: đúng khi di chuyển tự do mọi góc (8 hướng hoặc liên tục)
function euclidean(a, b) {
  return Math.sqrt((a.x - b.x) ** 2 + (a.y - b.y) ** 2);
}

4. So sánh Dijkstra vs A*

Sân chơi tương tác: Pathfinding Visualizer

Vẽ tường bằng cách click vào ô lưới, đặt điểm Bắt đầu/Đích, rồi chạy Dijkstra hoặc A* để xem thuật toán lan rộng vùng tìm kiếm — càng nhiều ô xanh nhạt được khám phá, thuật toán càng "tốn công" nhiều hơn để tìm ra đường đi màu vàng.