Thuật toán Dijkstra

Bách khoa toàn thư mở Wikipedia
Bước tới: menu, tìm kiếm

Thuật toán Dijkstra, mang tên của nhà khoa học máy tính người Hà Lan Edsger Dijkstra vào năm 1956 và ấn bản năm 1959[1], là một thuật toán giải quyết bài toán đường đi ngắn nhất nguồn đơn trong một đồ thị có hướng không có cạnh mang trọng số âm. Thuật toán thường được sử dụng trong định tuyến với một chương trình con trong các thuật toán đồ thị hay trong công nghệ Hệ thống định vị toàn cầu (GPS).

Bài toán[sửa | sửa mã nguồn]

Cho một đồ thị có hướng G=(V,E), một hàm trọng số w: E → [0, ∞) và một đỉnh nguồn s. Cần tính toán được đường đi ngắn nhất từ đỉnh nguồn s đến mỗi đỉnh của đồ thị.

Ví dụ: Chúng ta dùng các đỉnh của đồ thị để mô hình các thành phố và các cạnh để mô hình các đường nối giữa chúng. Khi đó trọng số các cạnh có thể xem như độ dài của các con đường (và do đó là không âm). Chúng ta cần vận chuyển từ thành phố s đến thành phố t. Thuật toán Dijkstra sẽ giúp chỉ ra đường đi ngắn nhất chúng ta có thể đi.

Trọng số không âm của các cạnh của đồ thị mang tính tổng quát hơn khoảng cách hình học giữa hai đỉnh đầu mút của chúng. Ví dụ, với 3 đỉnh A, B, C đường đi A-B-C có thể ngắn hơn so với đường đi trực tiếp A-C.

Giới thiệu thuật toán[sửa | sửa mã nguồn]

Xét đồ thị G =(X,E) với các cạnh có trọng số không âm. - Dữ liệu nhập cho thuật toán là ma trận trọng số L (với qui ước Lhk = +∞ nếu không có cạnh nối từ đỉnh h đến đỉnh k)và hai đỉnh x,y cho trước. - Dữ liệu xuất là đường đi ngắn nhất từ x đến y.

Chứng minh[sửa | sửa mã nguồn]

Ý tưởng của thuật toán được chứng minh như sau.

Chúng ta sẽ chỉ ra, khi một đỉnh v được bổ sung vào tập S, thì d[v] là giá trị của đường đi ngắn nhất từ nguồn s đến v.

Theo định nghĩa nhãn d, d[v] là giá trị của đường đi ngắn nhất trong các đường đi từ nguồn s, qua các đỉnh trong S, rồi theo một cạnh nối trực tiếp u-v đến v.

Giả sử tồn tại một đường đi từ s đến v có giá trị bé hơn d[v]. Như vậy trong đường đi, tồn tại đỉnh giữa s và v không thuộc S. Chọn w là đỉnh đầu tiên như vậy,

Mã giả[sửa | sửa mã nguồn]

Phân tích[sửa | sửa mã nguồn]

Với giải thuật đã mô tả ta dễ dàng thực hiện trực tiếp trên các đồ thị kích thước nhỏ,để có thể mã hóa và cài đặt hiệu quả cần đưa thêm các cấu trúc dữ liệu để sử dụng trong giải thuật.

Dữ liệu[sửa | sửa mã nguồn]

  • Hàm d(u) dùng để lưu trữ độ dài đường đi ngắn nhất từ đỉnh nguồn s đến đỉnh u. Rõ ràng d(s)= 0. Ký hiệu X^-(u) là tập tất cả các đỉnh có cạnh đi tới đỉnh u. Nếu với mọi v \in X^-(u) đã xác định được d(v) thì:
d(u)= min\{d(v)+w(v,u), v\in X^-(u)\}

.

  • Để tính được giá trị nhỏ nhất này, như thông thường khi khởi tạo ta phải gán cho d(v)=\infty, sau đó gặp giá trị nhỏ hơn thì thay thế lại.
  • Những đỉnh đã tính được d(v)hữu hạn được cho vào một hàng đợi có ưu tiên. Hàng đợi này luôn được bổ sung và sắp xếp lại nên một cấu trúc hợp lý là cấu trúc đống nhị phân (heap).
  • Để theo dõi trạng thái của các đỉnh trong quá trình xét, ta dùng hàm COLOR(u) xác định với mọi v\in V. Lúc đầu các đỉnh được tô màu trắng (WHITE), khi cho vào hàng đợi nó được tô màu xám (GRAY), khi đã tính xong khoảng cách nó được tô màu đen(BLACK).
  • Nếu cần ghi lại đường đi ta sẽ phải dùng một hàm con trỏ PRE(u) để chỉ đỉnh đứng ngay trước đỉnh u trên đường đi ngắn nhất từ s tới u.

Thời gian chạy[sửa | sửa mã nguồn]

Thuật toán Dijkstra bình thường sẽ có độ phức tạp là O(n^2+m). Tuy nhiên ta có thể sử dụng kết hợp với cấu trúc heap, khi đó độ phức tạp sẽ là O( (m+n)\log n ), nếu dùng đống Fibonacci thì độ phức tạp giảm xuống còn O( m + n\log n ). Trong đó m là số cạnh, n là số đỉnh của đồ thị đang xét.

Tham khảo[sửa | sửa mã nguồn]

  1. ^ Dijkstra, Edsger; Thomas J. Misa, Editor (tháng 8 năm 2010). “An Interview with Edsger W. Dijkstra”. Communications of the ACM 53 (8): 41–47. doi:10.1145/1787234.1787249. “What is the shortest way to travel from Rotterdam to Groningen? It is the algorithm for the shortest path which I designed in about 20 minutes. One morning I was shopping with my young fiancée, and tired, we sat down on the café terrace to drink a cup of coffee and I was just thinking about whether I could do this, and I then designed the algorithm for the shortest path.” 

Liên kết ngoài[sửa | sửa mã nguồn]