Bir grafiğin negatif ağırlıklı döngüleri varsa, Floyd-Warshall algoritması resmi olarak böyle bir grafik için geçerli değildir.
Aslında, aralarında negatif ağırlıklı bir döngüye girmenin imkansız olduğu i ve j köşe çiftleri için algoritma doğru şekilde çalışacaktır.
Yanıtı olmayan aynı köşe çiftleri için (aralarındaki yolda negatif bir döngünün varlığından dolayı), Floyd'un algoritması yanıt olarak bir sayı (muhtemelen çok olumsuz, ancak zorunlu değil) bulacaktır. Ancak Floyd'un algoritması, bu tür köşe çiftlerini düzgün bir şekilde işlemek ve örneğin \(- \infty\) çıktısı almak için geliştirilebilir.
Bunu yapmak için örneğin aşağıdaki ölçüt "yolun olmaması" yapılabilir. Bu grafik üzerinde olağan Floyd algoritmasının çalışmasına izin verin. O zaman i ve j köşeleri arasında en kısa yol yoktur, ancak ve ancak i 'den ulaşılabilen ve j'ye buradan ulaşılabilen bir t köşesi varsa, bunun için \(d [t][t]<0\).
Ayrıca Floyd'un algoritmasını negatif döngülere sahip grafikler için kullanırken, çalışma sürecinde ortaya çıkan mesafelerin her aşamada katlanarak negatif gidebileceği unutulmamalıdır. Bu nedenle, aşağıdan tüm mesafeleri bir değerle sınırlayarak tamsayı taşmasına karşı dikkatli olmalısınız (örneğin, \(- \infty\)).
Çözüm sözlü olarak şu şekilde açıklanabilir:
Floyd-Warshall algoritması giriş grafiği için çalıştıktan sonra, tüm köşe çiftleri \((i,j)\) üzerinde ve bu tür her bir çift için yineleme yapalım i den j e giden en kısa yolun sonsuzca küçük olup olmadığını kontrol ederiz. Bunu yapmak için, üçüncü t köşesi üzerinde yineleyelim ve eğer \(d[t][t] < 0\) (yani, negatif ağırlık döngüsünde yer alır) ve i ve j — bu durumda yol \((i,j)\) sonsuz uzunlukta olabilir.