Thuật toán tìm đường đi ngắn nhất

9.1 Nguyên tắc hoạt động của thuật toán Dijkstra

Thuật toán Dijkstra là một thuật toán để tìm đường đi ngắn nhất từ đỉnh bắt đầu đến tất cả các đỉnh khác trong đồ thị với trọng số các cạnh không âm. Thuật toán sử dụng phương pháp tham lam, chọn đỉnh có khoảng cách nhỏ nhất đã biết từ đỉnh bắt đầu tại mỗi bước và cập nhật khoảng cách đến các đỉnh kề.

Các bước của thuật toán:

1. Khởi tạo:

• Đặt khoảng cách đến đỉnh bắt đầu bằng 0.
• Đặt khoảng cách đến tất cả các đỉnh khác bằng vô cực.
• Tạo tập hợp các đỉnh chưa được thăm.

2. Chọn đỉnh hiện tại:

• Chọn đỉnh chưa được thăm có khoảng cách nhỏ nhất (đỉnh bắt đầu ở bước đầu tiên).

3. Cập nhật khoảng cách:

• Đối với mỗi đỉnh kề của đỉnh hiện tại, nếu đường mới qua đỉnh hiện tại ngắn hơn đường đã biết, cập nhật khoảng cách đến đỉnh đó.

4. Đánh dấu đỉnh hiện tại là đã thăm:

• Xóa đỉnh hiện tại khỏi tập hợp các đỉnh chưa được thăm.

5. Lặp lại các bước 2-4, cho đến khi tất cả các đỉnh đã được thăm hoặc đến đích.

Độ phức tạp thời gian và không gian của thuật toán Dijkstra:

Độ phức tạp thời gian:

O((V + E) log V) khi sử dụng priority queue (như heap Fibonacci), trong đó V là số đỉnh, E là số cạnh.

O(V^2) khi sử dụng danh sách đơn giản để lưu trữ khoảng cách.

Độ phức tạp không gian:

O(V) để lưu trữ khoảng cách và cha (để khôi phục đường đi).

9.2 Triển khai thuật toán Dijkstra

Triển khai thuật toán Dijkstra dài dòng, nhưng rất đơn giản. Khuyến khích bạn thử hiểu nó. Nếu thấy không rõ — hãy quay lại phần trên và đọc lại các bước chính của thuật toán.

Ví dụ triển khai thuật toán Dijkstra sử dụng priority queue (heap):

import heapq

def dijkstra(graph, start):
    # Khởi tạo
    distances = {vertex: float('infinity') for vertex in graph}
    distances[start] = 0
    priority_queue = [(0, start)]
    parents = {vertex: None for vertex in graph}
            
    while priority_queue:
        current_distance, current_vertex = heapq.heappop(priority_queue)
            
        # Nếu khoảng cách hiện tại lớn hơn khoảng cách đã ghi lại, bỏ qua đỉnh này
        if current_distance > distances[current_vertex]:
            continue
            
        # Cập nhật khoảng cách đến các đỉnh kề
        for neighbor, weight in graph[current_vertex].items():
            distance = current_distance + weight
            
            # Nếu tìm thấy đường ngắn hơn đến đỉnh kề
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                parents[neighbor] = current_vertex
                heapq.heappush(priority_queue, (distance, neighbor))
            
    return distances, parents
            
# Ví dụ sử dụng:
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}
}
start_vertex = 'A'
distances, parents = dijkstra(graph, start_vertex)
print("Khoảng cách ngắn nhất từ đỉnh bắt đầu:", distances)
print("Cha để khôi phục đường đi:", parents)

Output:

Khoảng cách ngắn nhất từ đỉnh bắt đầu: {'A': 0, 'B': 1, 'C': 3, 'D': 4}
Cha để khôi phục đường đi: {'A': None, 'B': 'A', 'C': 'B', 'D': 'C'}

9.3 Ví dụ bài toán giải quyết bằng thuật toán Dijkstra

Các ví dụ kinh điển về bài toán giải quyết bằng thuật toán Dijkstra:

1. Tối ưu hóa tuyến đường trong mạng lưới giao thông

Tìm đường đi ngắn nhất giữa các điểm trong mạng lưới giao thông (ví dụ, giữa các thành phố).

Ứng dụng:

Các hệ thống định vị, như Google Maps, sử dụng thuật toán Dijkstra để tính toán các tuyến đường tối ưu.

2. Lên kế hoạch tuyến đường giao hàng

Tối ưu hóa các tuyến đường cho dịch vụ giao hàng để giảm thiểu chi phí và thời gian giao hàng.

Ứng dụng:

Các công ty logistics sử dụng thuật toán Dijkstra để lập kế hoạch tuyến đường giao hàng và giảm thiểu chi phí vận hành.

3. Quản lý mạng lưới

Tối ưu hóa định tuyến gói dữ liệu trong mạng máy tính để giảm thiểu độ trễ và tăng băng thông.

Ứng dụng:

Các giao thức định tuyến như OSPF (Open Shortest Path First) sử dụng thuật toán Dijkstra để tìm các đường đi ngắn nhất trong mạng.

4. Phân tích mạng xã hội

Tìm các đường đi ngắn nhất và đo lường độ trung tâm trong các đồ thị xã hội (ví dụ, để tìm người dùng có ảnh hưởng nhất).

Ứng dụng:

Các nền tảng xã hội phân tích liên kết giữa người dùng để cung cấp các đề xuất và phân tích hoạt động mạng.

5. Trò chơi và thế giới ảo

Tìm đường đi cho nhân vật trong các thế giới trò chơi có chướng ngại và các mức độ khó khác nhau.

Ứng dụng:

Các engine game sử dụng thuật toán Dijkstra để tính toán chuyển động của nhân vật và đối tượng trong thế giới ảo.

6. Hệ thống quản lý năng lượng

Tối ưu hóa phân phối năng lượng trong mạng lưới điện để giảm thiểu tổn thất và đảm bảo độ tin cậy trong cung cấp.

Ứng dụng:

Các công ty năng lượng sử dụng thuật toán Dijkstra để tối ưu hóa các tuyến đường truyền tải năng lượng trong mạng lưới để giảm thiểu tổn thất năng lượng và tránh tình trạng quá tải.

Ví dụ:

Trong mạng lưới điện, mỗi nút đại diện cho một trạm chuyển tiếp, và các cạnh là các tuyến đường dẫn điện với các mức điện trở khác nhau. Thuật toán Dijkstra giúp tìm ra con đường có điện trở nhỏ nhất từ nguồn năng lượng đến người tiêu dùng.

7. Hệ thống sơ tán và lập kế hoạch đường đi

Tối ưu hóa các tuyến đường sơ tán trong các tòa nhà hoặc thành phố để đưa mọi người ra ngoài nhanh chóng và an toàn trong các tình huống khẩn cấp.

Ứng dụng:

Kiến trúc sư và kỹ sư sử dụng thuật toán Dijkstra để lên kế hoạch các tuyến đường sơ tán nhằm đảm bảo việc di dời người ra khỏi khu vực nguy hiểm một cách an toàn và nhanh chóng.

Ví dụ:

Trong một tòa nhà chung cư hoặc văn phòng, các nút trong đồ thị đại diện cho các phòng và hành lang, còn các cạnh là các tuyến đường giữa chúng. Thuật toán Dijkstra có thể được sử dụng để tìm đường ngắn nhất từ bất kỳ điểm nào trong tòa nhà đến lối ra gần nhất.