Deykstra alqoritmi mənfi tillərdə yanılır. Boşluğu iki klassik alqoritm doldurur: Bellman-Ford (bir mənbə, mənfi çəkilərə icazə, mənfi dövrləri aşkarlayır) və Floyd-Warshall (bütün cütlər arasında ən qısa yollar).
Mənfi til və mənfi dövr
Mənfi çəkili til (xərc əvəzinə qazanc) olar və ən qısa yollar yenə düzgün təyin olunur. Mənfi dövr cəmi mənfi olan dövrdür: hər dövrə yolu qısaldır, ona görə ən qısa yol mövcud deyil (-∞). Yaxşı alqoritm belə dövrü aşkarlamalıdır.
Bellman-Ford
Dövrsüz ən qısa yolda ən çox V - 1 til var. Ona görə bütün tilləri V - 1 dəfə relaksasiya etmək kifayətdir: k-cı keçiddən sonra dist ən çox k tilli bütün yollar üçün düzgündür. Bir əlavə keçid yoxlamadır: hələ də yaxşılaşan til varsa, başlanğıcdan mənfi dövr əlçatandır.
INF = float("inf")