Thuật toán Dijkstra

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

Lịch sử

Thuật toán Dijkstra được tạo ra trong khoảng hai mươi phút khi Edsger Dijkstra ngồi trên sân thượng ở Amsterdam cùng với vị hôn thê và đã trở thành một trong những nền tảng quan trọng giúp ông nổi tiếng.

Dijkstra đã phát minh thuật toán đường đi ngắn nhất khi làm việc tại Trung tâm Toán học ở Amsterdam vào năm 1956, nhằm giải quyết vấn đề đường đi ngắn nhất trên một bản đồ giao thông đơn giản hóa của Hà Lan. Ông đã triển khai thuật toán này trên máy tính ARMAC.

Bài toán về Đường Đi Ngắn Nhất

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ụ: Sử dụng các đỉnh của đồ thị để biểu diễn các thành phố và các cạnh để kết nối chúng. Khi đó trọng số các cạnh có thể hiểu như là độ 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 tìm ra đường đi ngắn nhất mà chúng ta có thể đi.

Trọng số không âm của các cạnh của đồ thị có ý nghĩa 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 về Thuật toán Dijkstra

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 L(h,k) = +∞ 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 về Thuật toá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 thêm 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 từ nguồn s, đi qua các đỉnh trong S, rồi qua một cạnh nối trực tiếp từ u đến v.

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

Mã giả của Thuật toán

Phân tích thuật toán

Với thuật toán đã mô tả, chúng ta có thể thực hiện trực tiếp trên các đồ thị nhỏ. Để mã hóa và triển khai hiệu quả, cần bổ sung các cấu trúc dữ liệu phù hợp trong giải thuật.

Dữ liệu đầu vào

• Hàm d(u) được sử dụng để lưu trữ độ dài của đường đi ngắn nhất từ đỉnh nguồn s đến đỉnh u. Rõ ràng d(s)= 0. Ký hiệu $X^{-<!--\; -\; -->}\left(u\right)$ là tập hợp tất cả các đỉnh có cạnh tới đỉnh u. Nếu với mọi $v\in <!--\; \in \; -->X^{-<!--\; -\; -->}\left(u\right)$
  đã xác định được d(v) thì:

.

• Để tính giá trị nhỏ nhất này, khi khởi tạo thường ta gán d(v)=$\mathrm{\infty <!--\; \infty \; -->}$, sau đó nếu gặp giá trị nhỏ hơn, ta thay thế lại.
• Những đỉnh đã có giá trị d(v) hữu hạn được đưa vào một hàng đợi ưu tiên. Hàng đợi này luôn được cập nhật và sắp xếp lại, do đó cấu trúc hợp lý là cấu trúc heap nhị phân (binary heap)...
• Để theo dõi trạng thái của các đỉnh trong quá trình xét, ta sử dụng hàm COLOR(u) xác định cho mọi $v\in <!--\; \in \; -->V$. Ban đầu, các đỉnh được đánh màu trắng (WHITE), khi được thêm vào hàng đợi sẽ chuyển sang màu xám (GRAY), và khi tính toán xong khoảng cách sẽ chuyển sang màu đen (BLACK).
• Nếu cần ghi lại đường đi, ta sẽ sử dụng hàm PRE(u) để chỉ định đỉnh trước đỉnh u trên đường đi ngắn nhất từ s tới u.

Thời gian thực thi

Thuật toán Dijkstra thông thường có độ phức tạp là $O(n^2+m)$. Tuy nhiên, sử dụng heap kết hợp, độ phức tạp sẽ là $O\left(\right(m+n\left)log\right(n\left)\right)$. Nếu sử dụng Fibonacci Heap, độ phức tạp giảm xuống còn $O(m+n\log <!--\; \; -->n)$. Trong đó, m là số cạnh và n là số đỉnh của đồ thị đang xét.

Liên kết ngoài