Tutorial — Shortest Route Accumulation

Ta nhận xét rằng việc tính toán lại đường đi ngắn nhất giữa mọi cặp nút sau mỗi lần xóa đỉnh là vô cùng đắt đỏ. Thay vì xử lý các bước xóa theo thứ tự xuôi, hãy thử đảo ngược thứ tự các thao tác.

Khi đảo ngược quá trình, thao tác xóa nút trở thành thao tác thêm dần từng nút vào mạng lưới. Khi thêm một nút mới $v$, khoảng cách ngắn nhất giữa hai nút bất kỳ chỉ có thể thay đổi nếu đường đi mới đi qua nút $v$ này.

Sử dụng ý tưởng của thuật toán Floyd-Warshall, mỗi khi thêm nút $v$, ta cập nhật độ trễ ngắn nhất giữa mọi cặp $(i, j)$ bằng công thức $d[i][j] = \min(d[i][j], d[i][v] + d[v][j])$. Sau đó, tính tổng $d[i][j]$ trên tất cả các cặp nút đã xuất hiện để thu được đáp án cho bước tương ứng.