Thuật toán của Dijkstra là một phương pháp phổ biến trong khoa học máy tính để tìm đường dẫn ngắn nhất giữa các nút trong đồ thị. Nó được áp dụng rộng rãi trong việc định tuyến, định vị bản đồ, và nhiều vấn đề tối ưu khác. Bài này đưa ra một tổng quát từng bước một về cách thực hiện tính toán bằng thuật toán Dijkstra để xác định con đường hiệu quả nhất.

Hiểu thuật toán

Thuật toán hoạt động bằng cách lặp lại việc chọn nút với khoảng cách nhỏ nhất, sau đó cập nhật khoảng cách đến các nút lân cận. Nó tiếp tục cho đến khi đường dẫn ngắn nhất đến nút đích được tìm thấy hoặc tất cả các nút đã được xử lý.

Tiến trình tính toán từng bước một

Giả sử chúng ta có một đồ thị với các nút A, B, C, D, và E, và các cạnh có trọng lượng sau:

  • A đến B: 4
  • A đến C: 2
  • B đến C: 1
  • B đến D: 5
  • C đến D: 8
  • C đến E: 10
  • D đến E: 2

Bắt đầu từ nút A, khởi tạo khoảng cách: A = 0, các điểm khác = vô cùng. Mark tất cả các nút là không có giám sát.

Lần lặp lại 1

Chọn nút A ( bán kính 0). Cập nhật nút nối B và C:

Khoảng cách đến B: 4 (A + 4), C: 2 (A + 2).

Lần lặp lại 2

Chọn nút C (đường 2). Cập nhật hàng xóm D và E:

Khoảng cách đến D: 10 (C + 8), đến E: 12 (C + 10).

Lần lặp lại 3

Chọn nút B ( vẽ 4). Cập nhật hàng xóm D:

Khoảng cách tới D: 9 (B + 5), là ít hơn 10. Cập nhật khoảng cách D đến 9. Mark B như được thăm.

Lần lặp lại 4

Chọn nút D ( vẽ 9). Cập nhật E

Khoảng cách tới E: 11 (D + 2) Cập nhật khoảng cách E đến 11. Mark D như được thăm.

Lần lặp lại 5

Điểm số E còn lại có khoảng cách 11 điểm, điểm E, đường ngắn nhất từ A đến E là qua nút C, B, D và E với khoảng cách tổng cộng 11.