Giới thiệu

Chào mừng bạn quay lại với loạt bài Thuật toán đồ thị! Dijkstra chạy nhanh, nhưng thuật toán này không hoạt động khi các cạnh có thể có trọng số âm. Bellman-Ford xử lý được trọng số âm và thậm chí có thể cho bạn biết khi đồ thị có chu trình âm.

Giống như Dijkstra, thuật toán này tìm khoảng cách ngắn nhất từ một đỉnh nguồn duy nhất. Đồ thị được cho dưới dạng n (các đỉnh từ 0 đến n - 1) và edges, một mảng phẳng gồm các bộ ba [u0, v0, w0, ...] biểu diễn các cạnh có hướng u -> v với trọng số w (trọng số có thể âm).

Các đỉnh không thể đến được sẽ được biểu thị bằng -1. Bắt đầu nào!