Nền tảng Kiến thức - Hành trang tới Tương lai
Card image

Chương 1-Bài 19. Tìm đường đi ngắn nhất bằng Thuật toán Dijkstra

Tác giả: Dương Nguyễn Phú Cường #11403
Ngày đăng: Hồi xưa đó
Lượt xem: 484

Thuật toán Dijkstra: Tìm đường đi ngắn nhất

Thuật toán Dijkstra là một trong những thuật toán cổ điển để giải quyết bài toán tìm đường đi ngắn nhất từ một điểm cho trước tới tất cả các điểm còn lại trong đồ thị có trọng số. Trong bài viết này chúng ta cùng tìm hiểu ý tưởng cơ bản của thuật toán Dijkstra.

1. Ý tưởng

Thuật toán Dijkstra có thể giải quyết bài toán tìm đường đi ngắn nhất trên đồ thị vô hướng lẫn có hướng miễn là trọng số không âm. Ý tưởng cơ bản của thuật toán như sau:
  • Bước 1: Từ đỉnh gốc, khởi tạo khoảng cách tới chính nó là 0, khởi tạo khoảng cách nhỏ nhất ban đầu tới các đỉnh khác là +\infty. Ta được danh sách các khoảng cách tới các đỉnh.
  • Bước 2: Chọn đỉnh a có khoảng cách nhỏ nhất trong danh sách này và ghi nhận. Các lần sau sẽ không xét tới đỉnh này nữa.
  • Bước 3: Lần lượt xét các đỉnh kề b của đỉnh a. Nếu khoảng cách từ đỉnh gốc tới đỉnh b nhỏ hơn khoảng cách hiện tại đang được ghi nhận thì cập nhật giá trị và đỉnh kề a vào khoảng cách hiện tại của b.
  • Bước 4: Sau khi xét tất cả đỉnh kề b của đỉnh a. Lúc này ta được danh sách khoảng cách tới các điểm đã được cập nhật. Quay lại Bước 2 với danh sách này. Thuật toán kết thúc khi chọn được khoảng cách nhỏ nhất từ tất cả các điểm.

2. Ví dụ

Để dễ dàng hiểu ý tưởng của thuật toán. Chúng ta cùng xem ví dụ với đồ thị vô hướng G. Thuật toán Dijkstra sẽ tìm khoảng cách từ đỉnh gốc 0 tới tất cả các đỉnh còn lại trong đồ thị G.
Đồ thị G
Đầu tiên, khởi tạo khoảng cách nhỏ nhất ban đầu tới các đỉnh khác là +\infty và khoảng cách tới đỉnh gốc là 0. Ta được danh sách các khoảng cách tới các đỉnh.
Chọn đỉnh 0 có giá trị nhỏ nhất, xét các đỉnh kề của đỉnh 0: Xét đỉnh 1, khoảng cách từ gốc đến đỉnh 1 là 2.5 < \infty nên ghi nhận giá trị mới là (2.5, 0) (nghĩa là khoảng cách đến đỉnh gốc hiện tại ghi nhận là 2.5, đỉnh kề liền trước là đỉnh 0). Xét tương tự cho đỉnh 2 và 3, ta được dòng thứ 2 trong bảng.
Sau khi xét tất cả các đỉnh ta chọn đỉnh 2 có khoảng cách nhỏ nhất và ghi nhận để xét tiếp. Tiếp tục xét đỉnh kề của 2 là đỉnh 4 và 5 với nguyên tắc nêu ở trên. Xét đỉnh 4, khoảng cách từ đỉnh gốc đến đỉnh 4 sẽ bằng khoảng cách từ đỉnh gốc tới đỉnh 2 cộng khoảng cách từ 2 đến 4. Nghĩa là 2.0+0.6=2.6 nên ta ghi nhận khoảng cách tại đỉnh 4 là (2.6, 2). Xét tương tự cho đỉnh 5.
Lúc này ta chọn được đỉnh 3 có khoảng cách nhỏ nhất, xét đỉnh kề của đỉnh 3 là đỉnh 5. Khoảng cách từ gốc tới đỉnh 5 =2.1+2.5=4.6 lớn hơn khoảng cách hiện tại được ghi nhận, vì vậy giá trị tại đỉnh 5 không đổi.
Đỉnh 1 là đỉnh được chọn tiếp theo, xét đỉnh kề của 1 là đỉnh 4. Khoảng cách từ đỉnh gốc không nhỏ hơn khoảng cách hiện tại nên ta không cập nhật gì ở đỉnh này.
Sau khi xét xong ta chọn được đỉnh 4 là đỉnh tiếp theo. Ta cập nhật giá trị mới cho đỉnh 6.
Chọn được đỉnh 5 là đỉnh nhỏ nhất, tiếp tục xét các đỉnh kề.
Đỉnh 6 là đỉnh tiếp theo được chọn.
Chọn đỉnh có khoảng cách nhỏ nhất là đỉnh 7.
Thuật toán kết thúc khi chọn được khoảng cách nhỏ nhất cho tất cả các đỉnh.

Chương trình học


  1. Lý thuyết đồ thị 31
    1. Các khái niệm cơ bản về Lý thuyết Đồ thị #11087
    2. Biểu diễn đồ thị trên máy tính bằng Ma trận kề #11112
    3. Biểu diễn đồ thị trên máy tính bằng Danh sách cạnh #11117
    4. Biểu diễn đồ thị trên máy tính bằng Danh sách kề #11116
    5. Lab 1 - Chuyển Danh sách cạnh sang Ma trận kề #11138
    6. Lab 1.2 - Chuyển Danh sách cạnh sang Danh sách kề #11144
    7. Lab 1.3 - Chuyển Ma trận kề sang Danh sách cạnh #11151
    8. Lab 1.4 - Chuyển Ma trận kề sang Danh sách kề #11154
    9. Lab 1.5 - Chuyển Danh sách kề sang Ma trận kề #11158
    10. Lab 1.6 - Chuyển Danh sách kề sang Danh sách cạnh #11161
    11. Duyệt cây theo chiều sâu DFS (Depth First Search) #10963
    12. Duyệt cây theo chiều rộng BFS (Breadth First Search) #11081
    13. Thuật toán Tìm đường đi giữa 2 đỉnh của Đồ thị bằng C/C++ #11079
    14. Lab 2 - Duyệt cây theo chiều sâu DFS (Depth First Search) #11167
    15. Lab 2.2 - Tìm đường đi bằng cách duyệt cây theo chiều sâu DFS (Depth First Search) #11168
    16. Lab 3 - Duyệt cây theo chiều rộng BFS (Breadth First Search) #11169
    17. Lab 3.2 - Tìm đường đi bằng cách duyệt cây theo chiều rộng BFS (Breadth First Search) #11170
    18. Lab 4 - Tìm các thành phần liên thông trên đồ thị vô hướng #11179
    19. Tìm đường đi ngắn nhất bằng Thuật toán Dijkstra #11403
    20. Lab 5 - Tìm đường đi ngắn nhất từ đỉnh S đến tất cả các đỉnh còn lại trên đồ thị (sử dụng thuật toán Dijkstra) #11418
    21. Lab 5.1 - Tìm đường đi ngắn nhất từ đỉnh S đến đỉnh T trên đồ thị (sử dụng thuật toán Dijkstra) #11423
    22. Thuật toán Kruskal – Tìm cây khung (bao trùm) nhỏ nhất #11485
    23. Lab 6 - Tìm cây khung (bao trùm) cực tiểu nhỏ nhất (sử dụng thuật toán Kruskal) #11486
    24. Thuật toán Prim - Tìm cây khung (bao trùm) nhỏ nhất #11516
    25. Lab 6.1 - Tìm cây khung (bao trùm) cực tiểu nhỏ nhất (sử dụng thuật toán PRIM) #11515
    26. Chu trình và đường đi Euler #11519
    27. Lab 7 - Tìm chu trình Euler #11520
    28. Lab 7.1 - Tìm đường đi Euler #11528
    29. Bài toán Luồng cực đại #11532
    30. Lab 8 - Tìm luồng cực đại - sử dụng thuật toán Ford - Fulkerson #11533
    31. Lab 8.1 - Tìm luồng cực đại - sử dụng thuật toán Edmonds - Karp (Shortest path) #11534
  2. Tài liệu tham khảo 2
    1. Kho sách, nguồn tài liệu tham khảo Lập trình C++ - Cấu trúc dữ liệu và Giải thuật #11100
    2. Bài tập Lý thuyết Đồ thị có lời giải #11547
  3. Quy hoạch động 1
    1. Lý thuyết các bài toán sử dụng Quy hoạch động #11567
Các bài học

Chương trình học

Bao gồm Module, Chương, Bài học, Bài tập, Kiểm tra...

Chương trình học


  1. Lý thuyết đồ thị 31
    1. Các khái niệm cơ bản về Lý thuyết Đồ thị #11087
    2. Biểu diễn đồ thị trên máy tính bằng Ma trận kề #11112
    3. Biểu diễn đồ thị trên máy tính bằng Danh sách cạnh #11117
    4. Biểu diễn đồ thị trên máy tính bằng Danh sách kề #11116
    5. Lab 1 - Chuyển Danh sách cạnh sang Ma trận kề #11138
    6. Lab 1.2 - Chuyển Danh sách cạnh sang Danh sách kề #11144
    7. Lab 1.3 - Chuyển Ma trận kề sang Danh sách cạnh #11151
    8. Lab 1.4 - Chuyển Ma trận kề sang Danh sách kề #11154
    9. Lab 1.5 - Chuyển Danh sách kề sang Ma trận kề #11158
    10. Lab 1.6 - Chuyển Danh sách kề sang Danh sách cạnh #11161
    11. Duyệt cây theo chiều sâu DFS (Depth First Search) #10963
    12. Duyệt cây theo chiều rộng BFS (Breadth First Search) #11081
    13. Thuật toán Tìm đường đi giữa 2 đỉnh của Đồ thị bằng C/C++ #11079
    14. Lab 2 - Duyệt cây theo chiều sâu DFS (Depth First Search) #11167
    15. Lab 2.2 - Tìm đường đi bằng cách duyệt cây theo chiều sâu DFS (Depth First Search) #11168
    16. Lab 3 - Duyệt cây theo chiều rộng BFS (Breadth First Search) #11169
    17. Lab 3.2 - Tìm đường đi bằng cách duyệt cây theo chiều rộng BFS (Breadth First Search) #11170
    18. Lab 4 - Tìm các thành phần liên thông trên đồ thị vô hướng #11179
    19. Tìm đường đi ngắn nhất bằng Thuật toán Dijkstra #11403
    20. Lab 5 - Tìm đường đi ngắn nhất từ đỉnh S đến tất cả các đỉnh còn lại trên đồ thị (sử dụng thuật toán Dijkstra) #11418
    21. Lab 5.1 - Tìm đường đi ngắn nhất từ đỉnh S đến đỉnh T trên đồ thị (sử dụng thuật toán Dijkstra) #11423
    22. Thuật toán Kruskal – Tìm cây khung (bao trùm) nhỏ nhất #11485
    23. Lab 6 - Tìm cây khung (bao trùm) cực tiểu nhỏ nhất (sử dụng thuật toán Kruskal) #11486
    24. Thuật toán Prim - Tìm cây khung (bao trùm) nhỏ nhất #11516
    25. Lab 6.1 - Tìm cây khung (bao trùm) cực tiểu nhỏ nhất (sử dụng thuật toán PRIM) #11515
    26. Chu trình và đường đi Euler #11519
    27. Lab 7 - Tìm chu trình Euler #11520
    28. Lab 7.1 - Tìm đường đi Euler #11528
    29. Bài toán Luồng cực đại #11532
    30. Lab 8 - Tìm luồng cực đại - sử dụng thuật toán Ford - Fulkerson #11533
    31. Lab 8.1 - Tìm luồng cực đại - sử dụng thuật toán Edmonds - Karp (Shortest path) #11534
  2. Tài liệu tham khảo 2
    1. Kho sách, nguồn tài liệu tham khảo Lập trình C++ - Cấu trúc dữ liệu và Giải thuật #11100
    2. Bài tập Lý thuyết Đồ thị có lời giải #11547
  3. Quy hoạch động 1
    1. Lý thuyết các bài toán sử dụng Quy hoạch động #11567

Bài học trước Bài học tiếp theo