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

Thuật toán Bellman-Ford là một trong những thuật toán cơ bản dùng để tìm đường đi ngắn nhất từ một đỉnh nguồn đến tất cả các đỉnh còn lại trong đồ thị. Điều đặc biệt của Bellman-Ford là nó có khả năng xử lý các đồ thị có trọng số cạnh âm, điều mà thuật toán Dijkstra không thể làm được.

Đặc điểm nổi bật của Bellman-Ford

1. Xử lý cạnh có trọng số âm: Đây là một trong những ưu điểm quan trọng của Bellman-Ford. Nó cho phép tìm đường đi ngắn nhất ngay cả trong trường hợp đồ thị chứa cạnh có trọng số âm.
2. Phát hiện đồ thị có chu trình âm: Ngoài việc tìm đường đi ngắn nhất, Bellman-Ford còn có khả năng phát hiện khi nào đồ thị chứa chu trình có tổng trọng số âm, giúp cảnh báo về tình trạng này.

Nguyên lý hoạt động

Thuật toán hoạt động bằng cách lặp qua tất cả các cạnh của đồ thị và thực hiện thao tác thư giãn (relaxation) trên các cạnh này. Thao tác thư giãn giúp cập nhật độ dài đường đi từ đỉnh nguồn đến đỉnh đích nếu có đường đi ngắn hơn hiện tại.

Trong một đồ thị có ( V ) đỉnh và ( E ) cạnh, thuật toán Bellman-Ford thực hiện ( V - 1 ) lần thư giãn các cạnh và kiểm tra chu trình âm lần cuối cùng.

Pseudo-code

Dưới đây là pseudo-code cho thuật toán Bellman-Ford:

function BellmanFord(graph, source):
    distance[] = initialize_single_source(graph, source)
    
    for i from 1 to |V| - 1:
        for each edge (u, v) in graph:
            if distance[u] + weight(u, v) < distance[v]:
                distance[v] = distance[u] + weight(u, v)
                
    for each edge (u, v) in graph:
        if distance[u] + weight(u, v) < distance[v]:
            error "Graph contains a negative-weight cycle"

    return distance[]

Cài đặt bằng ngôn ngữ lập trình Python

Dưới đây là một ví dụ về cách cài đặt thuật toán Bellman-Ford bằng Python:

class Graph:
    def __init__(self, vertices):
        self.V = vertices
        self.graph = []

    def add_edge(self, u, v, w):
        self.graph.append([u, v, w])

    def bellman_ford(self, src):
        distance = [float("Inf")] * self.V
        distance[src] = 0

        for _ in range(self.V - 1):
            for u, v, w in self.graph:
                if distance[u] != float("Inf") and distance[u] + w < distance[v]:
                    distance[v] = distance[u] + w

        for u, v, w in self.graph:
            if distance[u] != float("Inf") and distance[u] + w < distance[v]:
                print("Graph contains negative weight cycle")
                return

        self.print_solution(distance)

    def print_solution(self, distance):
        print("Vertex Distance from Source")
        for i in range(self.V):
            print(f"{i}\t\t{distance[i]}")

# Khởi tạo đồ thị với 5 đỉnh
g = Graph(5)
g.add_edge(0, 1, -1)
g.add_edge(0, 2, 4)
g.add_edge(1, 2, 3)
g.add_edge(1, 3, 2)
g.add_edge(1, 4, 2)
g.add_edge(3, 2, 5)
g.add_edge(3, 1, 1)
g.add_edge(4, 3, -3)

# Tìm đường đi ngắn nhất từ đỉnh 0
g.bellman_ford(0)

Giải thích mã nguồn

• Lớp Graph: Đại diện cho đồ thị với số lượng đỉnh và danh sách cạnh.
• add_edge(u, v, w): Thêm cạnh mới từ đỉnh ( u ) đến đỉnh ( v ) với trọng số ( w ).
• bellman_ford(src): Thực hiện thuật toán Bellman-Ford từ đỉnh nguồn ( src ) để tìm đường đi ngắn nhất.
• print_solution(distance): In ra kết quả khoảng cách từ đỉnh nguồn đến mỗi đỉnh còn lại.

Khi chạy đoạn mã trên, kết quả hiển thị sẽ là khoảng cách ngắn nhất từ đỉnh nguồn 0 đến các đỉnh khác. Ngoài ra, nếu đồ thị chứa chu trình âm, thông báo sẽ xuất hiện.

Việc áp dụng thuật toán Bellman-Ford trong thực tế rất quan trọng, đặc biệt trong các bài toán cần tính toán đường đi ngắn nhất mà trọng số cạnh có thể âm. Mặc dù không nhanh bằng một vài thuật toán khác, nhưng nhờ khả năng xử lý trọng số âm và phát hiện chu trình âm, Bellman-Ford là một công cụ mạnh mẽ trong nhiều ứng dụng thực tế.