Cho mạng có các liên kết có hướng trọng số dương. Dùng Bellman-Ford tính khoảng cách ngắn nhất từ router nguồn s tới mọi router.
Thuật toán: lặp tối đa n-1 vòng, mỗi vòng nới lỏng tất cả cạnh; dừng sớm nếu một vòng không có thay đổi.
Input:
4 4 1
1 2 3
2 3 4
1 3 10
3 4 2
Output:
1 0
2 3
3 7
4 9
Dòng 1: n m s.
m dòng: u v w — cạnh có hướng u → v trọng số w.
1 ≤ n ≤ 2000, 0 ≤ m ≤ 10^4, 1 ≤ w ≤ 10^4
n dòng: node dist cho node = 1..n. Không tới được in -1.
Ví dụ:
Đầu vào:
4 4 1
1 2 3
2 3 4
1 3 10
3 4 2
Đầu ra:
1 0
2 3
3 7
4 9
Giải thích:
Đang tải editor...