Thuật toán Dijkstra là một thuật toán tìm đường đi ngắn nhất trong một đồ thị có hướng và trọng số. Nó được sử dụng để tìm đường đi từ một đỉnh đầu tiên đến một đỉnh cuối cùng trong một đồ thị với các cạnh có trọng số.
Thuật toán Dijkstra tìm đường đi ngắn nhất bằng cách sử dụng một bảng giá trị để lưu trữ khoảng cách từ đỉnh đầu tiên đến các đỉnh khác trong đồ thị. Nó bắt đầu tại đỉnh đầu tiên và tìm kiếm đỉnh có khoảng cách từ đỉnh đầu tiên tới nó là nhỏ nhất. Sau đó, nó tiếp tục tìm kiếm đỉnh tiếp theo với khoảng cách từ đỉnh đầu tiên tới nó là nhỏ nhất. Quá trình này tiếp tục cho đến khi đến đỉnh cuối cùng.
Lịch sử thuật toán Dijkstra
Thuật toán Dijkstra được phát triển bởi Edsger W. Dijkstra, một nhà khoa học máy tính người Hà Lan, vào năm 1959. Ý tưởng của thuật toán là tìm đường đi ngắn nhất từ một đỉnh đến tất cả các đỉnh còn lại trong một đồ thị có trọng số. Ban đầu, thuật toán được sử dụng trong các mô hình lý thuyết cho máy tính, nhưng sau đó nó đã được áp dụng rộng rãi trong các lĩnh vực khác nhau, như vận tải, mạng lưới, và định tuyến. Hiện nay, thuật toán Dijkstra được coi là một trong những thuật toán quan trọng nhất trong lĩnh vực tìm đường đi.
Mô tả thuật toán Dijkstra
Thuật toán này duy trì một tập hợp các đỉnh có đường đi ngắn nhất từ nguồn đã được biết trước. Biểu đồ được biểu diễn bằng ma trận kề chi phí của nó, trong đó chi phí là trọng số của cạnh. Trong ma trận kề chi phí của biểu đồ, tất cả các giá trị đường chéo đều bằng không. Nếu không có đường dẫn nào từ đỉnh nguồn đến bất kỳ đỉnh nào khác Vi thì nó được biểu diễn bằng + ∞ Trong thuật toán này, chúng ta đã giả sử tất cả các trọng số đều dương.
Các bài viết liên quan:
- Ban đầu, không có đỉnh trong tập hợp.
- Đưa đỉnh nguồn Vs vào S. Xác định tất cả các đường đi từ Vs đến tất cả các đỉnh khác mà không đi qua bất kỳ đỉnh nào khác.
- Bây giờ, đưa đỉnh đó vào S gần với Vs nhất và tìm đường đi ngắn nhất đến tất cả các đỉnh qua đỉnh này và cập nhật các giá trị.
- Lặp lại bước cho đến khi n-1 đỉnh không được bao gồm trong S nếu có n đỉnh trong đồ thị.
Sau khi hoàn thành quá trình, chúng tôi nhận được đường đi ngắn nhất đến tất cả các đỉnh từ đỉnh nguồn.
Ví dụ: Tìm đường đi ngắn nhất giữa K và L trong biểu đồ được chỉ ra trong hình bằng cách sử dụng Thuật toán Dijkstra.
Phương pháp:
Bước 1: Đưa đỉnh K là S và xác định tất cả các đường đi trực tiếp từ K đến tất cả các đỉnh khác mà không đi qua đỉnh nào khác.
Khoảng cách đến tất cả các đỉnh khác
Bước 2: Đưa đỉnh trong S gần K nhất và xác định đường đi ngắn nhất đến tất cả các đỉnh qua đỉnh này và cập nhật các giá trị. Đỉnh gần nhất là c.
Khoảng cách đến tất cả các đỉnh khác
Bước 3: Đỉnh thứ 2 gần K nhất là 9, nằm trong S.
Khoảng cách đến tất cả các đỉnh khác
Bước 4: Đỉnh gần thứ 3 với K là b, nằm trong S.
Khoảng cách đến tất cả các đỉnh khác
Bước 5: Đỉnh gần nhất với K là d, nằm trong S.
Vì n-1 đỉnh thuộc S. Do đó ta tìm được khoảng cách ngắn nhất từ K đến tất cả các đỉnh khác. Như vậy, khoảng cách ngắn nhất giữa K và L là 8 và đường đi ngắn nhất là K, c, b, L.
Mã giả cho thuật toán Dijstra
Đây là mã giả về thuật toán Dijkstra sử dụng ngôn ngữ Python:
import heapq
def dijkstra(graph, start):
distances = {vertex: float('infinity') for vertex in graph}
distances[start] = 0
queue = [(0, start)]
while queue:
(distance, current) = heapq.heappop(queue)
if distance > distances[current]:
continue
for neighbor, weight in graph[current].items():
distance = distances[current] + weight
if distance < distances[neighbor]:
distances[neighbor] = distance
heapq.heappush(queue, (distance, neighbor))
return distances
graph = {
'A': {'B': 1, 'C': 4},
'B': {'A': 1, 'C': 2, 'D': 5},
'C': {'A': 4, 'B': 2, 'D': 1},
'D': {'B': 5, 'C': 1},
}
print(dijkstra(graph, 'A'))Trong mã giả này, graph là một đồ thị với các đỉnh và trọng số của các cạnh, và start là đỉnh bắt đầu tìm kiếm. Kết quả trả về là một từ điển với các khoảng cách từ start đến tất cả các đỉnh còn lại.
Đây là giải thích cho đoạn mã Python trên:
- Import thư viện
heapq: Thư viện này sử dụng để xử lý tập hợp ưu tiên (priority queue) trong thuật toán Dijkstra. - Định nghĩa hàm
dijkstra: Hàm này nhận vào đồ thịgraphvà đỉnh bắt đầustart. - Khởi tạo một từ điển
distances: Từ điển này chứa các khoảng cách từ đỉnhstartđến tất cả các đỉnh còn lại trong đồ thị. Ban đầu, tất cả các khoảng cách đều được đặt là vô cùng lớn. - Khởi tạo một hàng đợi
queue: Hàng đợi này sẽ chứa các cặp (khoảng cách, đỉnh) cần xử lý. Ban đầu, hàng đợi chỉ chứa một cặp (0,start), vì đỉnhstartcó khoảng cách là 0. - Vòng lặp while: Vòng lặp này sẽ lặp cho đến khi hàng đợi trống.
- Lấy ra phần tử đầu tiên của hàng đợi: Phần tử này là cặp (khoảng cách, đỉnh) có khoảng cách nhỏ nhất.
- So sánh khoảng cách với khoảng cách đã lưu trong từ điển
distances.
