Thuật toán DSA Bellman-Ford
Thuật toán Bellman-Ford
Thuật toán Bellman-Ford phù hợp nhất để tìm đường đi ngắn nhất trong đồ thị có hướng, với một hoặc nhiều trọng số cạnh âm, từ đỉnh nguồn đến tất cả các đỉnh khác.
Nó làm như vậy bằng cách liên tục kiểm tra tất cả các cạnh trong biểu đồ để tìm các đường đi ngắn hơn, với số lần bằng số đỉnh trong biểu đồ (trừ 1).
Thuật toán Bellman-Ford cũng có thể được sử dụng cho các đồ thị có cạnh dương (cả có hướng và vô hướng), giống như chúng ta có thể làm với thuật toán Dijkstra, nhưng thuật toán Dijkstra được ưa thích hơn trong những trường hợp như vậy vì nó nhanh hơn.
Sử dụng thuật toán Bellman-Ford trên đồ thị có chu kỳ âm sẽ không tạo ra kết quả là đường đi ngắn nhất vì trong chu trình âm, chúng ta luôn có thể đi thêm một vòng nữa và nhận được đường đi ngắn hơn.
Chu trình âm là đường đi mà chúng ta có thể đi theo đường tròn, trong đó tổng trọng số của các cạnh là âm.
May mắn thay, thuật toán Bellman-Ford có thể được triển khai để phát hiện và báo cáo một cách an toàn sự hiện diện của các chu kỳ tiêu cực.
Làm thế nào nó hoạt động:
- Đặt khoảng cách ban đầu thành 0 cho đỉnh nguồn và đặt khoảng cách ban đầu thành vô cùng cho tất cả các đỉnh khác.
- Đối với mỗi cạnh, hãy kiểm tra xem có thể tính được khoảng cách ngắn hơn hay không và cập nhật khoảng cách nếu khoảng cách được tính ngắn hơn.
- Kiểm tra tất cả các cạnh (bước 2) \(V-1\) lần. Số lần này bằng số đỉnh (\(V\)), trừ đi một.
- Tùy chọn: Kiểm tra chu kỳ âm. Điều này sẽ được giải thích chi tiết hơn sau.
Hoạt hình của thuật toán Bellman-Ford ở trên chỉ cho chúng ta thấy khi kiểm tra một cạnh dẫn đến khoảng cách được cập nhật, chứ không hiển thị tất cả các kiểm tra cạnh khác không dẫn đến khoảng cách được cập nhật.
Chạy qua thủ công
Thuật toán Bellman-Ford thực sự khá đơn giản vì nó kiểm tra tất cả các cạnh bằng cách sử dụng ma trận kề. Mỗi lần kiểm tra là để xem liệu có thể tạo ra khoảng cách ngắn hơn hay không bằng cách đi từ đỉnh ở một bên của cạnh, qua cạnh, đến đỉnh ở phía bên kia của cạnh.
Và việc kiểm tra tất cả các cạnh này được thực hiện \(V - 1\) lần, với \(V\) là số đỉnh trong biểu đồ.
Đây là cách thuật toán Bellman-Ford kiểm tra tất cả các cạnh trong ma trận kề trong biểu đồ của chúng tôi 5-1=4 lần:
Đã kiểm tra tất cả các cạnh 0 lần.
Bốn cạnh đầu tiên được kiểm tra trong biểu đồ của chúng tôi là A->C, A->E, B->C và C->A. Việc kiểm tra bốn cạnh đầu tiên này không dẫn đến bất kỳ cập nhật nào về khoảng cách ngắn nhất vì đỉnh bắt đầu của tất cả các cạnh này có khoảng cách vô hạn.
Sau khi kiểm tra các cạnh của đỉnh A, B và C, các cạnh của D cũng được kiểm tra. Vì điểm bắt đầu (đỉnh D) có khoảng cách 0 nên khoảng cách cập nhật cho A, B và C là trọng số của các cạnh đi ra từ đỉnh D.
Các cạnh tiếp theo cần kiểm tra là các cạnh đi ra từ đỉnh E, dẫn đến cập nhật khoảng cách cho đỉnh B và C.
Thuật toán Bellman-Ford hiện đã kiểm tra tất cả các cạnh 1 lần. Thuật toán sẽ kiểm tra tất cả các cạnh thêm 3 lần nữa trước khi kết thúc, vì Bellman-Ford sẽ kiểm tra tất cả các cạnh với số lần bằng số đỉnh trong đồ thị, trừ đi 1.
Thuật toán bắt đầu kiểm tra tất cả các cạnh lần thứ hai, bắt đầu bằng việc kiểm tra các cạnh đi ra từ đỉnh A. Việc kiểm tra các cạnh A->C và A->E không dẫn đến khoảng cách được cập nhật.
Cạnh tiếp theo cần kiểm tra là B->C, đi ra từ đỉnh B. Điều này dẫn đến khoảng cách cập nhật từ đỉnh D đến C là 5-4=1.
Kiểm tra cạnh tiếp theo C->A, dẫn đến khoảng cách cập nhật 1-3=-2 cho đỉnh A.
Việc kiểm tra cạnh C->A ở vòng 2 của thuật toán Bellman-Ford thực sự là lần kiểm tra cuối cùng dẫn đến khoảng cách được cập nhật cho biểu đồ cụ thể này. Thuật toán sẽ tiếp tục kiểm tra tất cả các cạnh thêm 2 lần nữa mà không cập nhật bất kỳ khoảng cách nào.
Việc kiểm tra tất cả các cạnh \(V-1\) lần trong thuật toán Bellman-Ford có vẻ như rất nhiều, nhưng việc này được thực hiện nhiều lần để đảm bảo rằng sẽ luôn tìm được khoảng cách ngắn nhất.
Triển khai thuật toán Bellman-Ford
Việc triển khai thuật toán Bellman-Ford rất giống với cách chúng tôi triển khai thuật toán Dijkstra .
Chúng tôi bắt đầu bằng cách tạo lớp Graph , trong đó các phương thức __init__ , add_edge và add_vertex sẽ được sử dụng để tạo biểu đồ cụ thể mà chúng tôi muốn chạy thuật toán Bellman-Ford để tìm đường đi ngắn nhất.
class Graph:
def __init__(self, size):
self.adj_matrix = [[0] * size for _ in range(size)]
self.size = size
self.vertex_data = [''] * size
def add_edge(self, u, v, weight):
if 0 <= u < self.size and 0 <= v < self.size:
self.adj_matrix[u][v] = weight
#self.adj_matrix[v][u] = weight # For undirected graph
def add_vertex_data(self, vertex, data):
if 0 <= vertex < self.size:
self.vertex_data[vertex] = data Phương thức bellman_ford cũng được đặt bên trong lớp Graph . Phương pháp này chạy thuật toán Bellman-Ford.
def bellman_ford(self, start_vertex_data):
start_vertex = self.vertex_data.index(start_vertex_data)
distances = [float('inf')] * self.size
distances[start_vertex] = 0
for i in range(self.size - 1):
for u in range(self.size):
for v in range(self.size):
if self.adj_matrix[u][v] != 0:
if distances[u] + self.adj_matrix[u][v] < distances[v]:
distances[v] = distances[u] + self.adj_matrix[u][v]
print(f"Relaxing edge {self.vertex_data[u]}-{self.vertex_data[v]}, Updated distance to {self.vertex_data[v]}: {distances[v]}")
return distancesDòng 18-19: Lúc đầu, tất cả các đỉnh được đặt có khoảng cách vô hạn tính từ đỉnh bắt đầu, ngoại trừ chính đỉnh bắt đầu, trong đó khoảng cách được đặt thành 0.
Dòng 21: Tất cả các cạnh đều được kiểm tra \(V-1\) lần.
Dòng 22-23: Vòng lặp for kép kiểm tra tất cả các cạnh trong ma trận kề. Với mọi đỉnh u , kiểm tra các cạnh đi đến đỉnh v .
Dòng 24-26: Nếu cạnh tồn tại và nếu khoảng cách tính toán ngắn hơn khoảng cách hiện tại, hãy cập nhật khoảng cách tới đỉnh đó v .
Mã hoàn chỉnh, bao gồm cả việc khởi tạo biểu đồ cụ thể của chúng tôi và mã để chạy thuật toán Bellman-Ford, trông như thế này:
Ví dụ
Trăn:
class Graph:
def __init__(self, size):
self.adj_matrix = [[0] * size for _ in range(size)]
self.size = size
self.vertex_data = [''] * size
def add_edge(self, u, v, weight):
if 0 <= u < self.size and 0 <= v < self.size:
self.adj_matrix[u][v] = weight
#self.adj_matrix[v][u] = weight # For undirected graph
def add_vertex_data(self, vertex, data):
if 0 <= vertex < self.size:
self.vertex_data[vertex] = data
def bellman_ford(self, start_vertex_data):
start_vertex = self.vertex_data.index(start_vertex_data)
distances = [float('inf')] * self.size
distances[start_vertex] = 0
for i in range(self.size - 1):
for u in range(self.size):
for v in range(self.size):
if self.adj_matrix[u][v] != 0:
if distances[u] + self.adj_matrix[u][v] < distances[v]:
distances[v] = distances[u] + self.adj_matrix[u][v]
print(f"Relaxing edge {self.vertex_data[u]}-{self.vertex_data[v]}, Updated distance to {self.vertex_data[v]}: {distances[v]}")
return distances
g = Graph(5)
g.add_vertex_data(0, 'A')
g.add_vertex_data(1, 'B')
g.add_vertex_data(2, 'C')
g.add_vertex_data(3, 'D')
g.add_vertex_data(4, 'E')
g.add_edge(3, 0, 4) # D -> A, weight 4
g.add_edge(3, 2, 7) # D -> C, weight 7
g.add_edge(3, 4, 3) # D -> E, weight 3
g.add_edge(0, 2, 4) # A -> C, weight 4
g.add_edge(2, 0, -3) # C -> A, weight -3
g.add_edge(0, 4, 5) # A -> E, weight 5
g.add_edge(4, 2, 3) # E -> C, weight 3
g.add_edge(1, 2, -4) # B -> C, weight -4
g.add_edge(4, 1, 2) # E -> B, weight 2
# Running the Bellman-Ford algorithm from D to all vertices
print("\nThe Bellman-Ford Algorithm starting from vertex D:")
distances = g.bellman_ford('D')
for i, d in enumerate(distances):
print(f"Distance from D to {g.vertex_data[i]}: {d}") Chạy ví dụ »Các cạnh tiêu cực trong thuật toán Bellman-Ford
Nói rằng thuật toán Bellman-Ford tìm ra "đường đi ngắn nhất" là không trực quan, bởi vì làm sao chúng ta có thể vẽ hoặc tưởng tượng những khoảng cách âm? Vì vậy, để dễ hiểu hơn, thay vào đó chúng ta có thể nói rằng đó là "con đường rẻ nhất " được tìm thấy với Bellman-Ford.
Trong thực tế, thuật toán Bellman-Ford chẳng hạn có thể giúp chúng ta tìm ra các tuyến đường giao hàng trong đó trọng số của cạnh biểu thị chi phí nhiên liệu và những thứ khác, trừ đi số tiền kiếm được bằng cách lái cạnh đó giữa hai đỉnh đó.
Với cách giải thích này, trọng số -3 ở cạnh C->A có thể có nghĩa là chi phí nhiên liệu là 5 đô la khi lái xe từ C đến A và chúng tôi được trả 8 đô la để nhận các gói hàng ở C và giao chúng ở A. Vì vậy, chúng tôi cuối cùng kiếm được nhiều hơn 3 đô la so với số tiền chúng ta chi tiêu. Do đó, bạn có thể kiếm được tổng cộng 2 USD bằng cách điều khiển tuyến đường giao hàng D->E->B->C->A trong biểu đồ trên của chúng tôi.
Chu kỳ âm trong thuật toán Bellman-Ford
Nếu chúng ta có thể đi các đường tròn trong đồ thị và tổng các cạnh trong đường tròn đó là âm thì chúng ta có một chu trình âm.
Bằng cách thay đổi trọng số trên cạnh C->A từ -3 thành -9, chúng ta nhận được hai chu kỳ âm: A->C->A và A->E->C->A. Và mỗi khi chúng tôi kiểm tra các cạnh này bằng thuật toán Bellman-Ford, khoảng cách chúng tôi tính toán và cập nhật ngày càng thấp hơn.
Vấn đề với chu kỳ âm là không tồn tại đường đi ngắn nhất, bởi vì chúng ta luôn có thể đi thêm một vòng nữa để có được đường đi ngắn hơn.
Đó là lý do tại sao việc triển khai thuật toán Bellman-Ford với việc phát hiện các chu kỳ âm là rất hữu ích.
Phát hiện các chu kỳ âm trong thuật toán Bellman-Ford
Sau khi chạy thuật toán Bellman-Ford, kiểm tra tất cả các cạnh trong biểu đồ \(V-1\) lần, tất cả các khoảng cách ngắn nhất đều được tìm thấy.
Tuy nhiên, nếu biểu đồ chứa các chu kỳ âm và chúng ta tiến hành thêm một vòng nữa để kiểm tra tất cả các cạnh, chúng ta sẽ tìm thấy ít nhất một khoảng cách ngắn hơn ở vòng cuối cùng này, phải không?
Vì vậy, để phát hiện chu kỳ âm trong thuật toán Bellman-Ford, sau khi kiểm tra tất cả các cạnh \(V-1\) lần, chúng ta chỉ cần kiểm tra tất cả các cạnh một lần nữa và nếu lần trước tìm thấy khoảng cách ngắn hơn thì chúng ta có thể kết luận rằng một chu kỳ tiêu cực phải tồn tại.
Dưới đây là phương pháp bellman_ford , bao gồm tính năng phát hiện chu kỳ âm, chạy trên biểu đồ ở trên với chu kỳ âm do trọng số cạnh C->A là -9:
Ví dụ
Trăn:
def bellman_ford(self, start_vertex_data):
start_vertex = self.vertex_data.index(start_vertex_data)
distances = [float('inf')] * self.size
distances[start_vertex] = 0
for i in range(self.size - 1):
for u in range(self.size):
for v in range(self.size):
if self.adj_matrix[u][v] != 0:
if distances[u] + self.adj_matrix[u][v] < distances[v]:
distances[v] = distances[u] + self.adj_matrix[u][v]
print(f"Relaxing edge {self.vertex_data[u]}->{self.vertex_data[v]}, Updated distance to {self.vertex_data[v]}: {distances[v]}")
# Negative cycle detection
for u in range(self.size):
for v in range(self.size):
if self.adj_matrix[u][v] != 0:
if distances[u] + self.adj_matrix[u][v] < distances[v]:
return (True, None) # Indicate a negative cycle was found
return (False, distances) # Indicate no negative cycle and return distancesDòng 30-33: Tất cả các cạnh được kiểm tra một lần nữa để xem có chu kỳ âm hay không.
Dòng 34: Trả về True chỉ ra rằng tồn tại một chu trình âm và None được trả về thay vì khoảng cách ngắn nhất, bởi vì việc tìm khoảng cách ngắn nhất trong biểu đồ có chu kỳ âm không có ý nghĩa gì (vì luôn có thể tìm thấy khoảng cách ngắn hơn bằng cách kiểm tra tất cả các cạnh một lần nữa).
Dòng 36: Trả về False có nghĩa là không có chu kỳ âm và distances có thể được trả về.
Trả về đường dẫn từ thuật toán Bellman-Ford
Chúng tôi hiện đang tìm tổng trọng số của các đường đi ngắn nhất, ví dụ: "Khoảng cách từ D đến A: -2" là kết quả của việc chạy thuật toán Bellman-Ford.
Nhưng bằng cách ghi lại đỉnh trước của mỗi đỉnh bất cứ khi nào một cạnh được thả lỏng, chúng ta có thể sử dụng điều đó sau này trong mã của mình để in kết quả bao gồm cả các đường đi ngắn nhất thực tế. Điều này có nghĩa là chúng tôi có thể cung cấp thêm thông tin trong kết quả của mình, với đường dẫn thực tế ngoài trọng số đường dẫn: "D->E->B->C->A, Khoảng cách: -2".
Ví dụ mã cuối cùng này là mã hoàn chỉnh cho thuật toán Bellman-Ford, với mọi thứ chúng ta đã thảo luận cho đến bây giờ: tìm trọng số của các đường đi ngắn nhất, phát hiện các chu kỳ âm và tìm các đường đi ngắn nhất thực tế:
Ví dụ
Trăn:
class Graph:
def __init__(self, size):
self.adj_matrix = [[0] * size for _ in range(size)]
self.size = size
self.vertex_data = [''] * size
def add_edge(self, u, v, weight):
if 0 <= u < self.size and 0 <= v < self.size:
self.adj_matrix[u][v] = weight
#self.adj_matrix[v][u] = weight # For undirected graph
def add_vertex_data(self, vertex, data):
if 0 <= vertex < self.size:
self.vertex_data[vertex] = data
def bellman_ford(self, start_vertex_data):
start_vertex = self.vertex_data.index(start_vertex_data)
distances = [float('inf')] * self.size
predecessors = [None] * self.size
distances[start_vertex] = 0
for i in range(self.size - 1):
for u in range(self.size):
for v in range(self.size):
if self.adj_matrix[u][v] != 0:
if distances[u] + self.adj_matrix[u][v] < distances[v]:
distances[v] = distances[u] + self.adj_matrix[u][v]
predecessors[v] = u
print(f"Relaxing edge {self.vertex_data[u]}->{self.vertex_data[v]}, Updated distance to {self.vertex_data[v]}: {distances[v]}")
# Negative cycle detection
for u in range(self.size):
for v in range(self.size):
if self.adj_matrix[u][v] != 0:
if distances[u] + self.adj_matrix[u][v] < distances[v]:
return (True, None, None) # Indicate a negative cycle was found
return (False, distances, predecessors) # Indicate no negative cycle and return distances
def get_path(self, predecessors, start_vertex, end_vertex):
path = []
current = self.vertex_data.index(end_vertex)
while current is not None:
path.insert(0, self.vertex_data[current])
current = predecessors[current]
if current == self.vertex_data.index(start_vertex):
path.insert(0, start_vertex)
break
return '->'.join(path)
g = Graph(5)
g.add_vertex_data(0, 'A')
g.add_vertex_data(1, 'B')
g.add_vertex_data(2, 'C')
g.add_vertex_data(3, 'D')
g.add_vertex_data(4, 'E')
g.add_edge(3, 0, 4) # D -> A, weight 4
g.add_edge(3, 2, 7) # D -> C, weight 7
g.add_edge(3, 4, 3) # D -> E, weight 3
g.add_edge(0, 2, 4) # A -> C, weight 4
g.add_edge(2, 0, -3) # C -> A, weight -3
g.add_edge(0, 4, 5) # A -> E, weight 5
g.add_edge(4, 2, 3) # E -> C, weight 3
g.add_edge(1, 2, -4) # B -> C, weight -4
g.add_edge(4, 1, 2) # E -> B, weight 2
# Running the Bellman-Ford algorithm from D to all vertices
print("\nThe Bellman-Ford Algorithm starting from vertex D:")
negative_cycle, distances, predecessors = g.bellman_ford('D')
if not negative_cycle:
for i, d in enumerate(distances):
if d != float('inf'):
path = g.get_path(predecessors, 'D', g.vertex_data[i])
print(f"{path}, Distance: {d}")
else:
print(f"No path from D to {g.vertex_data[i]}, Distance: Infinity")
else:
print("Negative weight cycle detected. Cannot compute shortest paths.") Chạy ví dụ » Dòng 19: Mảng predecessors giữ đỉnh tiền thân của mỗi đỉnh theo đường đi ngắn nhất.
Dòng 28: Mảng predecessors được cập nhật với đỉnh mới tiền thân mỗi khi một cạnh được thư giãn.
Dòng 40-49: Phương thức get_path sử dụng mảng predecessors để tạo chuỗi đường dẫn ngắn nhất cho mỗi đỉnh.
Độ phức tạp thời gian của thuật toán Bellman-Ford
Độ phức tạp về thời gian của thuật toán Bellman-Ford chủ yếu phụ thuộc vào các vòng lặp lồng nhau.
Vòng lặp for bên ngoài chạy \(V-1\) lần hoặc \(V\) lần trong trường hợp chúng ta cũng phát hiện chu kỳ âm. Đối với các đồ thị có nhiều đỉnh, việc kiểm tra tất cả các cạnh ít hơn một lần so với số đỉnh sẽ tạo ra sự khác biệt nhỏ, vì vậy chúng ta có thể nói rằng vòng lặp bên ngoài đóng góp \(O(V)\) vào độ phức tạp về thời gian.
Hai vòng lặp for bên trong kiểm tra tất cả các cạnh trong biểu đồ. Nếu chúng ta giả sử một trường hợp xấu nhất về độ phức tạp thời gian, thì chúng ta có một đồ thị rất dày đặc trong đó mỗi đỉnh có một cạnh với mọi đỉnh khác, do đó, với tất cả các đỉnh \(V\) cạnh với tất cả các đỉnh khác \(V\ ) phải được kiểm tra, điều này góp phần làm tăng độ phức tạp về thời gian.
Vì vậy, tổng cộng, chúng ta có được độ phức tạp về thời gian cho thuật toán Bellman-Ford:
\[ O(V^3) \]
Tuy nhiên, trong các tình huống thực tế và đặc biệt đối với các đồ thị thưa thớt, nghĩa là mỗi đỉnh chỉ có các cạnh đối với một phần nhỏ của các đỉnh khác, độ phức tạp về thời gian của hai vòng lặp for bên trong kiểm tra tất cả các cạnh có thể xấp xỉ từ \(O(V^2) \) đến \(O(E)\) và chúng tôi nhận được tổng độ phức tạp về thời gian cho Bellman-Ford:
\[ O(V \cdot E) \]
Độ phức tạp về thời gian của thuật toán Bellman-Ford chậm hơn so với thuật toán Dijkstra, nhưng Bellman-Ford có thể tìm đường đi ngắn nhất trong đồ thị có cạnh âm và nó có thể phát hiện các chu kỳ âm, điều mà thuật toán Dijkstra không thể làm được.
