Nếu một biểu đồ có các chu kỳ có trọng số âm, thì chính thức thuật toán Floyd-Warshall không thể áp dụng cho biểu đồ đó.
Trên thực tế, đối với các cặp đỉnh i j mà giữa chúng không thể nhập một chu trình có trọng số âm, thuật toán sẽ hoạt động chính xác.
Đối với các cặp đỉnh giống nhau mà không có đáp số (do có chu trình âm trên đường đi giữa chúng), thuật toán Floyd sẽ tìm một số nào đó (có thể âm mạnh, nhưng không nhất thiết) làm đáp án. Tuy nhiên, thuật toán của Floyd có thể được cải thiện để xử lý gọn gàng các cặp đỉnh như vậy và xuất ra ví dụ: \(- \infty\).
Để làm điều này, ví dụ: có thể thực hiện tiêu chí "không tồn tại đường dẫn" sau đây. Vì vậy, hãy để thuật toán Floyd thông thường hoạt động trên biểu đồ này. Khi đó, không có đường đi ngắn nhất giữa các đỉnh i và j if và chỉ khi có một đỉnh t có thể tới được từ i và từ đó có thể tới được j, với \(d [t][t]<0\).
Ngoài ra, khi sử dụng thuật toán Floyd cho đồ thị có chu kỳ âm, cần nhớ rằng khoảng cách phát sinh trong quá trình làm việc có thể âm theo cấp số nhân theo từng pha. Do đó, bạn nên cẩn thận chống tràn số nguyên bằng cách giới hạn tất cả các khoảng cách từ bên dưới đến một giá trị nào đó (ví dụ: \(- \infty\)).
Giải pháp có thể được mô tả bằng lời nói như sau:
Sau khi thuật toán Floyd-Warshall hoạt động cho đồ thị đầu vào, hãy lặp lại trên tất cả các cặp đỉnh \((i,j)\) và cho từng cặp như vậy chúng tôi kiểm tra, vô hạn đường đi ngắn nhất từ i đến j có nhỏ hay không. Để làm điều này, hãy lặp qua đỉnh thứ ba t và nếu nó trở thành \(d[t][t] < 0\) (tức là nó nằm trong chu kỳ có trọng số âm) và có thể truy cập được từ i và j — thì đường dẫn \((i,j)\) có thể có độ dài vô cùng nhỏ.