Khám phá về thuật toán Dijkstra, cách tìm đường đi ngắn nhất

Với khả năng giải quyết bài toán tìm đường đi ngắn nhất trên đồ thị có trọng số, thuật toán Dijkstra đã trở thành một công cụ quan trọng trong việc tối ưu hóa các vấn đề liên quan đến giao thông, quản lý tài nguyên hay định tuyến mạng.

Tổng quan về thuật toán Dijkstra

Thuật toán Dijkstra hoạt động trên nguyên tắc duyệt qua các đỉnh của đồ thị theo thứ tự khoảng cách ngắn nhất từ đỉnh xuất phát, mở rộng từ đỉnh này đến các đỉnh kề tiếp theo có chi phí thấp nhất và duy trì một bộ đường đi ngắn nhất tới các đỉnh đã xét.

thuật toán Dijkstra - hình 1

Nguyên lý hoạt động

1. Khởi tạo:

Bắt đầu từ đỉnh xuất phát, gán giá trị khoảng cách bằng 0.
Gán giá trị khoảng cách cho tất cả các đỉnh còn lại là +∞.
Tạo một tập hợp trống để lưu trữ các đỉnh đã được xử lý.

2. Lặp lại:

Chọn đỉnh chưa được xử lý có khoảng cách nhỏ nhất (ban đầu là đỉnh xuất phát).
Cập nhật khoảng cách cho các đỉnh kề của đỉnh hiện tại. Nếu khoảng cách từ đỉnh hiện tại đến đỉnh kề qua một cạnh nhỏ hơn giá trị khoảng cách đã biết, cập nhật khoảng cách này.
Đánh dấu đỉnh hiện tại là đã xử lý.

3. Kết thúc: Quá trình tiếp tục lặp lại cho đến khi tất cả các đỉnh đã được xử lý hoặc khoảng cách đến đích đã được tối ưu.

thuật toán Dijkstra - hình 2

Ví dụ đồ thị chi tiết

Giả sử chúng ta có một đồ thị như sau:

thuật toán Dijkstra - hình 3

Các đỉnh bao gồm A, B, C, D, E.

Các cạnh và trọng số sẽ là:

A - B: 6.
A - D: 1.
B - D: 2.
B - E: 2.
B - C: 5.
D - E: 1.
E - C: 5.

Chúng ta sẽ sử dụng thuật toán Dijkstra để tìm đường đi ngắn nhất từ đỉnh A đến các đỉnh khác.

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

Đỉnh xuất phát: A.
Khoảng cách từ A đến A: 0.
Khoảng cách từ A đến các đỉnh khác: ∞.
Tập hợp đỉnh đã xử lý: rỗng.

Bảng khoảng cách ban đầu như sau:

Đỉnh	Khoảng cách từ A
A	0
B	∞
C	∞
D	∞
E	∞

Bước 2: Chọn đỉnh có khoảng cách nhỏ nhất chưa được xử lý

Đỉnh A có khoảng cách nhỏ nhất (0), chọn A.
Đánh dấu A là đã xử lý.

Bước 3: Cập nhật khoảng cách đến các đỉnh kề của A

Đỉnh kề của A là B (khoảng cách 6), D (khoảng cách 1).
Cập nhật khoảng cách từ A đến B là min(∞, 0 + 6) = 6.
Cập nhật khoảng cách từ A đến D là min(∞, 0 + 1) = 1.

Ta có bảng khoảng cách sau bước 3 dưới đây:

Đỉnh	Khoảng cách từ A
A	0
B	6
C	∞
D	1
E	∞

Bước 4: Lặp lại

Chọn đỉnh có khoảng cách nhỏ nhất chưa được xử lý là D (1).
Đánh dấu D là đã xử lý.

Bước 5: Cập nhật khoảng cách đến các đỉnh kề của D

Đỉnh kề của D là B (khoảng cách 2), E (khoảng cách 1).
Cập nhật khoảng cách từ A đến B là min(6, 1 + 2) = 3.
Cập nhật khoảng cách từ A đến E là min(∞, 1 + 1) = 2.

Bảng khoảng cách sau bước 5:

Đỉnh	Khoảng cách từ A
A	0
B	3
C	∞
D	1
E	2

Bước 6: Lặp lại

Chọn đỉnh có khoảng cách nhỏ nhất chưa được xử lý, ta có E (2).
Đánh dấu E là đã xử lý.

Bước 7: Cập nhật khoảng cách đến các đỉnh kề của E

Đỉnh kề của E ta có B (khoảng cách 2), C (khoảng cách 5).
Cập nhật khoảng cách từ A đến B có min(3, 2 + 2) = 3 (không thay đổi).
Cập nhật khoảng cách từ A đến C là min(∞, 2 + 5) = 7.

Bảng khoảng cách sau bước 7:

Đỉnh	Khoảng cách từ A
A	0
B	3
C	7
D	1
E	2

Bước 8: Lặp lại

Chọn đỉnh có khoảng cách nhỏ nhất chưa được xử lý, ta có B (3).
Đánh dấu B là đã xử lý.

Bước 9: Cập nhật khoảng cách đến các đỉnh kề của B

Đỉnh kề của B đến C (khoảng cách 5).
Cập nhật khoảng cách từ A đến C là min(7, 3 + 5) = 7 (không thay đổi).

Bảng khoảng cách sau bước 9 như sau:

Đỉnh	Khoảng cách từ A
A	0
B	3
C	7
D	1
E	2

Bước 10: Lặp lại

Chọn đỉnh có khoảng cách nhỏ nhất chưa được xử lý là C (7).
Đánh dấu C là đã xử lý.

Tất cả các đỉnh đã được xử lý, thuật toán kết thúc.

Kết quả cuối cùng

Đỉnh	Khoảng cách từ A	Đường đi ngắn nhất từ A
A	0	A
B	3	A → D → B
C	7	A → D → E → C
D	1	A → D
E	2	A → D → E

Các ứng dụng trong đời sống của thuật toán Dijkstra

Tìm đường đi ngắn nhất trong giao thông, logistic

Trong lĩnh vực giao thông, thuật toán Dijkstra được sử dụng rộng rãi tại các hệ thống định tuyến và dẫn đường như GPS, ứng dụng bản đồ trên điện thoại thông minh hay phần mềm lập kế hoạch tuyến đường cho các hãng vận tải. Trong logistic, thuật toán Dijkstra được ứng dụng để tối ưu hóa quá trình vận chuyển hàng hóa. Các công ty logistic có thể sử dụng thuật toán này để lập kế hoạch tuyến đường hiệu quả nhất cho các phương tiện vận chuyển, tối thiểu hóa khoảng cách di chuyển cũng như chi phí vận hành. Thuật toán này đặc biệt quan trọng đối với các hoạt động logistic quy mô lớn, khi việc di chuyển bằng một quãng đường ngắn có thể tăng thêm lợi nhuận đáng kể.

thuật toán Dijkstra - hình 4

Định tuyến mạng

Thuật toán Dijkstra được sử dụng rộng rãi trong các giao thức định tuyến mạng như OSPF (Open Shortest Path First) và IS-IS (Intermediate System to Intermediate System), giúp các thiết bị mạng tính toán, xây dựng bảng định tuyến với đường đi ngắn nhất đến các mạng đích. Nhờ vậy, dữ liệu có thể được truyền hiệu quả, tránh được tình trạng quá tải hay lãng phí băng thông mạng.

thuật toán Dijkstra - hình 5

Quản lý tài nguyên trong hệ thống phân tán

Thuật toán Dijkstra được áp dụng trong hệ thống phân tán bằng cách biểu diễn hệ thống phân tán dưới dạng một đồ thị có trọng số, trong đó các nút là các máy tính và các cạnh là những kết nối mạng có trọng số tương ứng với thông số như băng thông, độ trễ, chi phí. Sau đó, thuật toán Dijkstra được sử dụng để tính toán đường đi ngắn nhất từ nút nguồn đến các nút cung cấp tài nguyên mục tiêu, tối ưu hóa việc sử dụng tài nguyên.

thuật toán Dijkstra - hình 6

Ứng dụng trong kỹ thuật hàng không vũ trụ

Đối với ngành hàng không, các đường bay được biểu diễn dưới dạng một đồ thị, trong đó các sân bay là các đỉnh và tuyến đường bay là các cạnh. Trọng số của các cạnh có thể biểu diễn khoảng cách, thời gian bay, chi phí nhiên liệu hoặc những yếu tố khác tùy theo mục tiêu tối ưu hóa. Thuật toán Dijkstra được sử dụng để tìm ra quỹ đạo bay ngắn nhất, hiệu quả nhất giữa hai sân bay để tiết kiệm thời gian, chi phí cũng như giảm thiểu lượng khí thải.

thuật toán Dijkstra - hình 7

Tạm kết

Thuật toán Dijkstra là một trong những thuật toán cơ bản và quan trọng nhất trong lĩnh vực khoa học máy tính, đặc biệt là khi cần giải quyết các bài toán tìm đường đi ngắn nhất trên đồ thị có trọng số không âm. Hy vọng với các thông tin trong bài, bạn sẽ có thêm nhiều kiến thức hữu ích hơn!

Nếu bạn là một lập trình viên đang cần tìm thiết bị công nghệ cao để hỗ trợ cho công việc, đừng quên tham khảo các sản phẩm như máy tính bảng, điện thoại, hay PC,… với những ưu đãi hấp dẫn tại website của FPT Shop nhé. Danh sách các sản phẩm laptop bán chạy nhất của cửa hàng: