Thuật toán Dijkstra

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, là một 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 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).

Lịch sử

Đâu là con đường ngắn nhất để đi từ Rotterdam đến Groningen, hay nói chung: từ thành phố này đến thành phố nhất định. Đây là thuật toán tìm đường đi ngắn nhất, mà tôi đã thiết kế trong khoảng hai mươi phút. Vào một buổi sáng đi mua sắm ở Amsterdam cùng vị hôn thê trẻ tuổi với sự mệt mỏi, chúng tôi ngồi trên sân thượng để uống một tách cà phê và tôi chỉ nghĩ liệu tôi có thể làm điều này không, và sau đó tôi đã thiết kế thuật toán tìm đường đi ngắn nhất. Như tôi đã nói, đó là một phát minh trong hai mươi phút. Trên thực tế, nó đã được xuất bản vào năm 1959, ba năm sau đó. Các ấn phẩm vẫn có thể đọc được, quả thật như vậy, và khá đẹp. Một trong những lý do khiến nó rất hay là tôi đã thiết kế nó mà không cần bút chì và giấy. Sau này tôi đã học được rằng một trong những lợi thế của việc thiết kế mà không cần bút chì và giấy là bạn gần như buộc phải tránh đi mọi sự phức tạp có thể tránh được. Cuối cùng, thuật toán đó đã trở thành một trong những nền tảng giúp tôi nổi tiếng, với sự kinh ngạc lớn của tôi. —Edsger Dijkstra trong một cuộc phỏng vấn với Philip L. Frana, Communications of the ACM, 2001.

Dijkstra đã nghĩ về bài toán đường đi ngắn nhất khi làm việc tại Trung tâm Toán học ở Amsterdam năm 1956 với tư cách là một lập trình viên để chứng minh khả năng của một máy tính mới có tên ARMAC. Mục tiêu của ông là chọn cả một bài toán và giải pháp (sẽ được tạo bởi máy tính) mà những người không thuần tính toán vẫn có thể hiểu được. Ông đã thiết kế thuật toán đường đi ngắn nhất và sau đó triển khai nó cho ARMAC bằng bản đồ giao thông được đơn giản hóa một chút của 64 thành phố ở Hà Lan. Một năm sau, ông gặp một vấn đề khác từ các kỹ sư phần cứng làm việc trên máy tính tiếp theo của học viện: giảm thiểu lượng dây cần thiết để kết nối các chân trên bảng điều khiển phía sau của máy. Như một giải pháp, ông đã phát hiện lại thuật toán Prim (được biết đến trước đó với Jarník, và cũng được Prim khám phá lại). Dijkstra đã xuất bản thuật toán vào năm 1959, 2 năm sau Prim và 29 năm sau Jarník.

Bài toá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

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

Ý 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ả

Phân tích

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

• 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

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 Fibonacci Heap 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.

Liên kết ngoài

• Oral history interview with Edsger W. Dijkstra, Charles Babbage Institute University of Minnesota, Minneapolis.
• Dijkstra's Algorithm in C#
• Fast Priority Queue Implementation of Dijkstra's Algorithm in C#
• Applet by Carla Laffra of Pace University
• Animation of Dijkstra's algorithm
• Visualization of Dijkstra's Algorithm
• Shortest Path Problem: Dijkstra's Algorithm Lưu trữ 2007-09-27 tại Wayback Machine
• Dijkstra's Algorithm Applet
• Open Source Java Graph package with implementation of Dijkstra's Algorithm
• Haskell implementation of Dijkstra's Algorithm on Bonsai code
• QuickGraph, Graph Data Structures and Algorithms for.NET Lưu trữ 2018-01-21 tại Wayback Machine
• Implementation in Boost C++ library
• Implementation in T-SQL
• A Java library for path finding with Dijkstra's Algorithm and example applet Lưu trữ 2015-03-07 tại Wayback Machine
• A MATLAB program for Dijkstra's algorithm Lưu trữ 2012-12-18 tại Wayback Machine
• Dijkstra's Algorithm in C Programming Language Lưu trữ 2014-12-31 tại Wayback Machine