Một trong những thuật toán nổi tiếng trong lập trình đó là thuật toán Dijkstra tìm đường đi ngắn nhất. Trong cuộc sống của con người có rất nhiều công việc được các chương trình máy tính mô phỏng và giải bằng thuật toán này. Dưới đây là những kiến thức cơ bản về ý tưởng và mô tả của thuật toán nổi tiếng này.
Tổng quan về thuật toán Dijkstra tìm đường đi ngắn nhất
Để hiểu được thuật toán Dijkstra thì trước hết cần hiểu được tổng quan về nó qua các thuật ngữ cơ bản sau:
- Graph (đồ thị): Đồ thị được định nghĩa là G =(V,E) là một cấu trúc dữ liệu phi tuyến tính, trong đó V là tập hợp hữu hạn các đỉnh (node), E là tập hợp hữu hạn các cạnh nối giữa hai đỉnh với nhau
- Weighted graph (đồ thị có trọng số): Đồ thị có trọng số tức là đồ thị mà mỗi cạnh sẽ được gán thêm một trọng số.
- Connected graph (đồ thị liên thông): Một đồ thị được gọi là liên thông (connected) nếu nó có đường đi giữa mọi cặp đỉnh phân biệt của đồ thị. Ngược lại với đồ thị này là đồ thị không liên thông
- Spanning tree (cây khung): spanning tree là cây con của đồ thị G, chứa mọi đỉnh của G.
Ý tưởng thực hiện 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 được dựa trên nguyên tắc giảm bớt. Trong đó được thực hiện theo quy trình các giá trị chính xác hơn sẽ dần thay thế cho một giá trị gần đúng với khoảng cách chính xác cho đến khi nào đạt được khoảng cách ngắn nhất. Khoảng cách gần đúng tới mỗi đỉnh được ước tính sẽ lớn hơn nhiều khoảng cách thực và sẽ dần được thay thế bằng giá trị nhỏ nhất của giá trị cũ và bằng độ dài của một đường mới tìm được.
Mô tả thuật toán Dijkstra tìm đường đi ngắn nhất
Để hiểu rõ hơn về ý tưởng thuật toán Dijkstra, sau đây FPT Aptech sẽ phân tích từng bước của Thuật toán Dijkstra tìm đường đi ngắn nhất qua đồ thị bên dưới để làm ví dụ:
Như bạn đã biết, thuật toán của Dijkstra là một thuật toán tham lam tức là bạn sẽ đi con đường ngắn hơn từ đỉnh cho trước đến đỉnh kia và thuật toán sẽ hoàn tất khi bạn truy cập tất cả các đỉnh của đồ thị. Dưới đây là các bước để hoàn thành thuật toán Dijkstra:
Bước 1:
Bạn sẽ bắt đầu với nút A và lúc này có 2 con đường:
- Con đường đầu tiên là đi từ A đến B với độ dài là 5
- Và đi từ A đến C với độ dài là 3.
Do đó, bạn có thể viết trong danh sách kế bên các đỉnh đã truy cập là 2 đỉnh (B, C) và trọng số tương ứng để đến đó. Sau đó, theo nguyên tắc, bạn sẽ chọn con đường từ A đến C.
Bước 2:
Khi bạn truy cập vào đỉnh C, bạn có thể thấy rằng lúc này có 3 đường đi khác nhau:
- Con đường đầu tiên là đi từ C đến B
- Con đường thứ hai là đi từ C đến D
- Con đường thứ ba là đi từ C đến E
Tiếp tục ghi vào danh sách hai đỉnh mới đồng thời chọn con đường ngắn nhất là đi từ C đến B.
Bước 3:
Bây giờ tại B, bạn lại có 3 đường:
- B đến D
- B đến E
- Và B quay lại C
Bạn chọn con đường ngắn nhất là đi từ B đến D và cập nhật vào danh sách trọng số mới các đường đi từ nút A đến các đỉnh khác. Lúc này bạn có thể thấy là không có đường đi mới nào từ D đến E. Trong trường hợp này, bạn quay lại đỉnh trước đó để kiểm tra đường đi ngắn nhất.
Bước 4:
Lúc này sẽ có một đường đi với độ dài là 4 đi đến E và một đường đi đến C. Bạn có thể chọn bất kỳ đường nào chúng ta thích.
Cuối cùng, bạn có thể thấy rằng bất kỳ phương án nào bạn đi trên đường từ đỉnh A đến E đều có trọng số như nhau vì các đường đi ngắn nhất đã được ghi trong danh sách. Và bạn có thể thấy tất cả các đường đi mà bạn đã sử dụng.
Trên đây là mô tả đơn giản nhất về thuật toán Dijkstra tìm đường đi ngắn nhất. Hiểu và thực hành được thuật toán này sẽ giúp bạn có cơ sở để giải các thuật toán phức tạp hơn, ngày càng chuyên nghiệp hơn trong công việc lập trình của mình. Chúc bạn sớm đạt được những thành công trong lĩnh vực này.
✔️✔️Tìm hiểu thêm: https://www.besport.com/post/41765263