Tìm đường đi ngắn nhất dùng thuật toán dijkstra

Chào mừng các bạn đến với bài tập ngày hôm này nhé!

Hôm nay,ta sẽ đến với một bài toán khá là kinh điển-tìm đường đi ngắn nhất ,hehe thấy vậy thôi chứ người ta làm được từ thời nào ời,giờ mình chỉ việc tham khảo và học lại thôi.Về bài toán này có rất nhiều thuật toán hỗ trợ chúng ta lập trình.Thì trong bài viết này mình sẽ giới thiệu cho các bạn thuật toán dijkstra.Và không thể làm gì khác hơn lúc này đó là tìm hiểu ngay nó là gì và nó làm việc như thế nào nhé!

Khái niệ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:

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.

Phân tích mã giả:

  • 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ọiX^{-}(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)= vô cùng lớn, 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 thuộc 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.
                               Procedure Dijsktra(G: Có trọng số và liên thông,s: Đỉnh nguồn) 
                                Begin R:=V;
                                 For eachvinR do 
                                 Begin L[v]: = ∞; P[v]: = -; 
                                 end 
                                 L[s]=0; 
                                 While (R≠) 
                                     Begin     
                                      v = Đỉnh trong R có L[v] nhỏ nhất; 
                                      R=R-{v} 
                                      For eachi in (R Tập đỉnh kề với v) do 
                                      If (L[i]> L[v]+w[v][i]) then 
                                          L[i]:=L[v]+w[v][i]; 
                                          P[i]=v;
                                       end 
                               End

Trên đó là phần lý thuyết mình đã tham khảo trên wiki,trong phần code mình sắp chia sẽ cho các bạn đây mình sẽ làm bài tổng quát nêu trên và thêm 2 bài toán khác bao gồm:

1.Tận dụng lại bài toán tổng quát,viết chương trình tìm đường đi ngắn nhất giữa 2 đỉnh;
2.Tận dụng lại bài toán ở câu 1 để viết chương trình tìm đường đi ngắn nhất giữa 3 đỉnh (đường đi từ a đến c là ngắn nhất và đường đi này phải đi qua b)

Đây là phần code của mình, có chú thích cho các bạn rồi,các bạn xem xem có hiểu không nhé,nếu có thắc đừng quên comment bạn nhé,nếu mình chậm trả lời thì liên hệ facebook mình hổ trợ trực tiếp luôn nè.

Chúc các bạn hoàn thành tốt bài tập này nhé!

Lưu ý là thuật toán trên mình tự code nên chắc chắn không thể không có sai sót nên mong các bạn thông cảm và chỉ dùng để tham khảo thôi nhé.

Giấy phép Creative Commons Giấy phép Creative Commons Attribution-ShareAlike 4.0 Quốc tế .

Tạo tài khoản



Đăng nhập


Quên mật khẩu

Hoặc là :