Thuật toán Ford-Bellman
Hãy cho một đồ thị có trọng số trực tiếp G với các đỉnh n và các cạnh m và một số đỉnh bắt đầu v . Cần tìm độ dài của các đường đi ngắn nhất từ đỉnh v đến tất cả các đỉnh khác.
Giống như Dijkstra, Ford-Bellman tìm kiếm khoảng cách từ đỉnh 1 đến tất cả các đỉnh khác, nhưng hoạt động với các cạnh âm.
Bản thân thuật toán Ford-Bellman bao gồm một số giai đoạn ( n-1). Ở mỗi giai đoạn, tất cả các cạnh của biểu đồ đều được kiểm tra và thuật toán sẽ cố gắng thư giãn dọc theo từng cạnh (a, b) của chi phí c. Thư giãn dọc theo bờ vực — đây là một nỗ lực để cải thiện ý nghĩa của d[a] giá trị d[b] + c. Trên thực tế, điều này có nghĩa là chúng tôi đang cố gắng cải thiện câu trả lời cho đỉnh bằng cách sử dụng cạnh và câu trả lời hiện tại cho top.
Mảng d là một mảng có độ dài ngắn nhất tính từ đỉnh bắt đầu, giống như trong Dijkstra, ban đầu chúng ta điền nó với số lượng lớn nhất có thể, ngoại trừ đỉnh bắt đầu mà bạn cần đặt 0.
Để lưu trữ các cạnh, không sử dụng ma trận kề hoặc ma trận trọng số mà sử dụng một danh sách cho biết cạnh rời khỏi nút nào ( từ), nơi nó đến ( đến) và trọng số của nó (chi phí).
cạnh cấu trúc {
int from, to, cost;
};
vectơ<cạnh> cạnh;
Hằng số INF biểu thị số "vô cực" - nó phải được chọn theo cách rõ ràng vượt quá tất cả các độ dài đường dẫn có thể có.
Việc thực hiện đơn giản nhất của thuật toán:
d[v] = 0;
cho (int i=0; i<n-1; ++i)
cho (int j=0; j<m; ++j)
nếu (d[cạnh[j].từ] <INF)
d[edges[j].to] = min(d[edges[j].to], d[edges[j].from] + Edges[j].cost);
hoặc ngắn hơn một chút bằng cú pháp C++11:
d[v] = 0;
cho (int i=0; i< n-1; ++i)
cho (cạnh j: các cạnh)
nếu (d[j.từ] <INF)
d[j.to] = min(d[j.to], d[j.from] + j.cost);
Ví dụ công việc
Lấy một đồ thị có hướng đơn giản với 5 nút, 4 cạnh có trọng số bằng 1.
Hãy giới thiệu một danh sách các cạnh theo thứ tự đó.
4 5 1
3 4 1
2 3 1
1 2 1
Các giá trị ban đầu trong mảng có độ dài ngắn nhất:
| 0 |
inf |
inf |
inf |
inf |
trong đó inf phải là một số nguyên khớp luôn lớn hơn trọng số của cạnh.
Sau lần đầu tiên
| 0 |
1 |
inf |
inf |
inf |
Sau lần thứ 2
| 0 |
1 |
2 |
inf |
inf |
Sau lần thứ 3
| 0 |
1 |
2 |
3 |
inf |
Sau lần thứ 4
| 0 |
1 |
2 |
3 |
4 |
Nếu chúng tôi cung cấp các cạnh theo thứ tự từ 1 đến cuối cùng, chúng tôi có thể tìm thấy độ dài ngắn nhất sau lần chạy đầu tiên.
|