Cài đặt thuật toán Johnson trong lập trình

Thuật toán Johnson là một giải pháp mạnh mẽ trong lý thuyết đồ thị, giúp tính toán đường đi ngắn nhất giữa mọi cặp đỉnh trong đồ thị có trọng số. Khác với các thuật toán như Floyd-Warshall và Dijkstra, thuật toán này có ưu điểm là hiệu quả hơn trong một số trường hợp nhất định. Ứng dụng thuật toán Johnson trong lập trình đòi hỏi hiểu biết về các cấu trúc dữ liệu và những bước cụ thể để thực thi thuật toán. Dưới đây là cách để hiện thực hóa thuật toán Johnson trong lập trình.

Khái quát về thuật toán Johnson

Thuật toán này kết hợp hai thuật toán nổi tiếng khác: Bellman-Ford và Dijkstra. Bellman-Ford được sử dụng để phát hiện các chu trình âm và tính lại trọng số cạnh, trong khi Dijkstra được sử dụng để tìm đường đi ngắn nhất từ mỗi đỉnh đến tất cả các đỉnh khác.

Các bước thực hiện

1. Thêm đỉnh mới: Thêm một đỉnh giả s vào đồ thị, kết nối s với tất cả các đỉnh khác bằng các cạnh có trọng số 0.

2. Chạy thuật toán Bellman-Ford: Sử dụng thuật toán Bellman-Ford từ đỉnh s để tính toán trọng số tiềm năng của các đỉnh. Nếu phát hiện chu trình âm, thuật toán sẽ dừng lại.

3. Thiết lập trọng số lại (Reweighting): Sử dụng giá trị tiềm năng từ bước Bellman-Ford để tái trọng số các cạnh, đảm bảo rằng tất cả các cạnh đều có trọng số không âm.

4. Chạy thuật toán Dijkstra: Sử dụng thuật toán Dijkstra từ mỗi đỉnh trong đồ thị gốc để tính toán đường đi ngắn nhất với trọng số được tái trọng số.

5. Khôi phục trọng số gốc: Chuyển đổi kết quả cuối cùng trở lại với trọng số gốc để hoàn tất tính toán.

Ví dụ Cụ thể trong Python

Dưới đây là một ví dụ đơn giản về cách cài đặt thuật toán Johnson trong Python:

import heapq
import sys

def johnson(graph):
    def bellman_ford(graph, start):
        dist = {v: float('inf') for v in graph}
        dist[start] = 0
        
        for i in range(len(graph) - 1):
            for u in graph:
                for v, w in graph[u]:
                    if dist[u] + w < dist[v]:
                        dist[v] = dist[u] + w
        
        for u in graph:
            for v, w in graph[u]:
                if dist[u] + w < dist[v]:
                    return None  # Negative-weight cycle detected
        
        return dist
    
    def dijkstra(graph, start):
        dist = {v: float('inf') for v in graph}
        dist[start] = 0
        priority_queue = [(0, start)]
        
        while priority_queue:
            current_dist, u = heapq.heappop(priority_queue)
            
            if current_dist > dist[u]:
                continue
            
            for v, weight in graph[u]:
                distance = current_dist + weight
                if distance < dist[v]:
                    dist[v] = distance
                    heapq.heappush(priority_queue, (distance, v))
        
        return dist
    
    new_graph = {v: graph[v][:] for v in graph}
    new_graph['s'] = [(v, 0) for v in graph]

    potential = bellman_ford(new_graph, 's')
    if potential is None:
        print("Negative-weight cycle detected")
        return
    
    reweighted_graph = {}
    for u in graph:
        reweighted_graph[u] = []
        for v, weight in graph[u]:
            reweighted_weight = weight + potential[u] - potential[v]
            reweighted_graph[u].append((v, reweighted_weight))
    
    shortest_paths = {}
    for u in graph:
        shortest_paths[u] = dijkstra(reweighted_graph, u)
        
        for v in graph:
            if shortest_paths[u][v] < float('inf'):
                shortest_paths[u][v] += potential[v] - potential[u]
    
    return shortest_paths

# Example usage
if __name__ == "__main__":
    graph = {
        'A': [('B', -1), ('C', 4)],
        'B': [('C', 3), ('D', 2), ('E', 2)],
        'C': [],
        'D': [('B', 1), ('C', 5)],
        'E': [('D', -3)]
    }
    
    print(johnson(graph))

Lời Kết

Việc triển khai thuật toán Johnson trong lập trình giúp giải quyết hiệu quả vấn đề đường đi ngắn nhất giữa mọi cặp đỉnh trong đồ thị. Đây là một thuật toán kết hợp thông minh giữa Bellman-Ford và Dijkstra, tận dụng ưu điểm của cả hai để đạt được kết quả tối ưu hơn trong nhiều tình huống. Hiểu sâu về thuật toán và các bước thực hiện sẽ giúp lập trình viên dễ dàng triển khai thuật toán này vào hệ thống của họ.