Trước tiên, hãy xem xét thuật toán Floyd. Gọi ~dis_{u,v}~ là khoảng cách ngắn nhất từ ~u~ đến ~v~. Ban đầu, ~dis_{u,v} = e_{u,v}~. Ta lặp qua mỗi đỉnh từ ~1~ đến ~n~, và khi đến đỉnh ~i~, ta cập nhật cho mọi cặp đỉnh ~j, k~: ~dis_{j,k} = \min(dis_{j,k}, dis_{j,i} + dis_{i,k})~.

Chúng ta nhận thấy rằng thuật toán Floyd có một đặc điểm: khi vòng lặp ngoại cùng đến điểm ~k~ (chưa bắt đầu vòng lặp lần thứ ~k~), ~dis_{u,v}~ biểu thị cho đường đi ngắn nhất từ ~u~ đến ~v~ và chỉ đi qua các điểm có số thứ tự trong khoảng ~\left[1, k\right)~.

Vì vậy, trong quá trình lặp, với mỗi ~k~, ta duyệt qua tất cả các cặp ~(i, j)~ thỏa mãn ~i < k~, ~j < i~ và cập nhật câu trả lời. Độ dài chu trình này là ~d(i, j) + a(i, k) + a(j, k)~. Độ phức tạp là ~O(n^3)~.