Thuật toán Dijkstra và các cách thực thi

Trong bài viết này, ta sẽ cùng tìm hiểu về thuật toán Dijkstra với các ví dụ là các hình vẽ minh họa, đoạn giả mã của thuật toán này cùng với các ứng dụng của nó.

Thuật toán Dijkstra

Thuật toán Dijkstra cho phép chúng ta tìm đường đi ngắn nhất giữa hai đỉnh bất kỳ của đồ thị. Nó khác với cây khung nhỏ nhất vì khoảng cách ngắn nhất giữa hai đỉnh có thể không bao gồm tất cả các đỉnh của đồ thị.

Cách thức hoạt động của thuật toán như sau:

• Thuật toán Dijkstra hoạt động dựa trên cơ sở bất kỳ đường đi con nào từ B tới D của đường đi ngắn nhất từ A đến D giữa các đỉnh A và D cũng là đường đi ngắn nhất giữa các đỉnh B và D.
• Djikstra đã sử dụng thuộc tính này theo hướng ngược lại, tức là chúng ta ước tính vượt qua khoảng cách của mỗi đỉnh từ đỉnh đầu tiên. Sau đó, chúng ta sẽ truy cập từng nút và các nút lân cận của nó để tìm đường đi con ngắn nhất đến các nút lân cận đó.
• Thuật toán sử dụng cách tiếp cận tham lam, tức là chúng ta sẽ tìm ra giải pháp tốt nhất tiếp theo với hy vọng rằng kết quả cuối cùng là giải pháp tốt nhất cho toàn bộ vấn đề.

Ví dụ về thuật toán

• Giả sử ta có một đồ thị chứa các trọng số như sau:

• Chọn một đỉnh bắt đầu và gán giá trị vô cực cho tất cả các nút khác.

• Đi đến từng đỉnh và cập nhật độ dài đường đi của nó.

• Nếu độ dài đường đi của đỉnh liền kề nhỏ hơn độ dài đường đi mới, không thực hiện cập nhật cho nó.

• Không thực hiện cập nhật độ dài đường đi của các đỉnh đã được truy cập.

• Sau mỗi lần lặp, chúng ta chọn đỉnh chưa được duyệt có độ dài đường đi nhỏ nhất. Vì vậy, chúng ta sẽ chọn 5 trước 7.

• Lưu ý rằng đỉnh ngoài cùng bên phải có độ dài đường đi được cập nhật hai lần.

• Lặp lại cho đến khi tất cả các đỉnh đã được duyệt.

Đoạn giả mã cho thuật toán

Chúng ta cần duy trì khoảng cách đường đi của mỗi đỉnh. Chúng ta có thể lưu trữ nó trong một mảng có kích thước v, trong đó v là số đỉnh.

Chúng ta cũng muốn có thể đi được con đường ngắn nhất, không chỉ biết độ dài của con đường ngắn nhất. Đối với điều này, chúng ta sẽ ánh xạ mỗi đỉnh với đỉnh được cập nhật lần cuối cùng độ dài đường đi của nó.

Sau khi thuật toán kết thúc, chúng ta có thể quay ngược lại từ đỉnh đích đến đỉnh nguồn để tìm đường đi. Một hàng đợi ưu tiên nhỏ nhất có thể được sử dụng để nhận đỉnh có khoảng cách đường đi nhỏ nhất một cách hiệu quả.

• Hàm dijkstra với tham số đầu vào là (G, S)
  • Sử dụng vòng lặp for cho mỗi đỉnh V trong G
    • Gán khoảng cách[V] ← giá trị vô cực
    • Gán phần trước[V] ← giá trị NULL
    • Nếu V != S, thực hiện thêm V vào trong hàng đợi ưu tiên Q
  • Gán khoảng cách[S] ← 0
• Trong khi Q không rỗng
  • Gán U ← Giá trị MIN được lấy từ Q
  • Vòng lặp for với mỗi nút chưa được duyệt V của U
    • Gán khoảng cách tạm thời ← khoảng cách[U] + trọng số cạnh(U, V)
    • Nếu khoảng cách tạm thời < khoảng cách[V]
      • Gán khoảng cách[V] ← Khoảng cách tạm thời
      • Gán phần trước[V] ← U
• Trả về mảng khoảng cách[], mảng thành phần trước[]

Độ phức tạp của thuật toán Dijkstra

• Độ phức tạp về thời gian: . Trong đó, E là số cạnh và V là số đỉnh.
• Độ phức tạp về không gian:

Các ứng dụng của thuật toán Dijkstra

• Được sử dụng để tìm con đường đi ngắn nhất.
• Được sử dụng trong các ứng dụng mạng xã hội.
• Được ứng dụng trong mạng điện thoại.
• Được ứng dụng để tìm các vị trí trong bản đồ.

Trên đây là khái niệm và ví dụ cơ bản về thuật toán Dijkstra. Hy vọng mọi người có thể áp dụng vào trong chương trình của mình. Nếu mọi người có đóng góp gì thêm thì có thể để các bình luận bên dưới bài viết này. Mọi người hãy tiếp tục theo dõi các bài tiếp theo và cập nhật các bài mới nhất trên tek4 nhé!

P/s: Cảm ơn mọi người!