Jika graf mempunyai kitaran berat negatif, maka secara rasmi algoritma Floyd-Warshall tidak boleh digunakan untuk graf sedemikian.
Malah, bagi pasangan bucu i dan j tersebut, yang antaranya mustahil untuk memasuki kitaran berat negatif, algoritma akan berfungsi dengan betul.
Untuk pasangan bucu yang sama yang tiada jawapan (disebabkan kehadiran kitaran negatif pada laluan di antara mereka), algoritma Floyd akan menemui beberapa nombor (mungkin sangat negatif, tetapi tidak semestinya) sebagai jawapan. Walau bagaimanapun, algoritma Floyd boleh dipertingkatkan untuk mengendalikan pasangan bucu sedemikian dengan kemas dan keluaran cth. \(- \infty\).
Untuk melakukan ini, sebagai contoh, kriteria "ketidakwujudan laluan" berikut boleh dilakukan. Jadi, biarkan algoritma Floyd biasa berfungsi pada graf ini. Kemudian tiada laluan terpendek antara bucu i dan j jika dan hanya jika terdapat bucu t boleh dicapai dari i dan dari mana j boleh dicapai, yang mana \(d [t][t]<0\).
Selain itu, apabila menggunakan algoritma Floyd untuk graf dengan kitaran negatif, perlu diingat bahawa jarak yang timbul dalam proses kerja boleh pergi secara negatif, secara eksponen dengan setiap fasa. Oleh itu, anda harus berhati-hati terhadap limpahan integer dengan mengehadkan semua jarak dari bawah kepada beberapa nilai (contohnya, \(- \infty\)).
Secara lisan, penyelesaian boleh diterangkan seperti berikut:
Selepas algoritma Floyd-Warshall berfungsi untuk graf input, mari kita ulangi semua pasangan bucu \((i,j)\), dan untuk setiap pasangan tersebut kami periksa, tidak terhingga laluan terpendek dari i ke j adalah kecil atau tidak. Untuk melakukan ini, mari kita ulangi pada puncak ketiga t, dan jika ia ternyata menjadi \(d[t][t] < 0\) (iaitu ia terletak pada kitaran berat negatif), dan ia boleh dicapai daripada i dan j — maka laluan \((i,j)\) boleh mempunyai panjang yang tidak terhingga.