THUẬT TOÁN DIJKSTRA – TÌM ĐƯỜNG ĐI NGẮN NHẤT

THUẬT TOÁN DIJKSTRA – TÌM ĐƯỜNG ĐI NGẮN NHẤT

Dijkstra là thuật toán 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 trong đồ thị có trọng số không âm.

---

📌 Ý tưởng chính

• Giống như bạn đứng ở đỉnh xuất phát, từ từ mở rộng sang các đỉnh gần nhất, luôn chọn đường ngắn nhất đã biết để đi tiếp.

---

🧮 Các bước thực hiện

Giả sử đồ thị có:

• Tập đỉnh: V

• Trọng số các cạnh: w(u,v)

Bước 1 – Khởi tạo:

• Gán khoảng cách từ đỉnh nguồn $s$ đến chính nó là 0, tất cả các đỉnh khác là ∞

• Đánh dấu tất cả các đỉnh là chưa được thăm

• Tạo tập đỉnh Q chứa tất cả các đỉnh

---

Bước 2 – Lặp:

• Trong khi $Q$ chưa rỗng:

  1. Chọn đỉnh $u\in Q$ có khoảng cách nhỏ nhất

  2. Đánh dấu $u$ là đã thăm, loại khỏi $Q$

  3. Với mỗi đỉnh kề $v$ của $u$, nếu đường đi qua $u$ ngắn hơn:

     Neˆˊu dist[u]+w(u,v)<dist[v] thıˋ cập nhật dist[v

---

✅ Ví dụ minh họa nhỏ

Giả sử đồ thị:

Các cạnh:

• AB = 1

• AD = 2

• BD = 1

• BC = 4

Tìm đường đi ngắn nhất từ A đến các đỉnh khác.

Khởi tạo:

Lặp:

• Chọn A (0):

  • B: 0+1 = 1 → cập nhật dist[B] = 1

  • D: 0+2 = 2 → cập nhật dist[D] = 2

• Chọn B (1):

  • D: 1+1 = 2 (không đổi)

  • C: 1+4 = 5 → dist[C] = 5

• Chọn D (2): không cải thiện gì

• Chọn C (5): xong

Kết quả:

---

🛠 Ứng dụng thực tế

• GPS tìm đường đi ngắn nhất

• Lập trình game (AI di chuyển)

• Mạng máy tính, định tuyến (routing protocols)