Se un grafico ha cicli di peso negativo, formalmente l'algoritmo di Floyd-Warshall non è applicabile a tale grafico.
Infatti, per quelle coppie di vertici i e j, tra le quali è impossibile inserire un ciclo di peso negativo, l'algoritmo funzionerà correttamente.
Per le stesse coppie di vertici per le quali non c'è risposta (a causa della presenza di un ciclo negativo sul percorso tra di loro), l'algoritmo di Floyd troverà un numero (possibilmente fortemente negativo, ma non necessariamente) come risposta. Tuttavia, l'algoritmo di Floyd può essere migliorato per gestire tali coppie di vertici in modo ordinato e generare un output, ad esempio, \(- \infty\).
Per fare ciò, ad esempio, si può applicare il seguente criterio "non esistenza del percorso". Quindi, lascia che il solito algoritmo di Floyd funzioni su questo grafico. Allora non esiste cammino minimo tra i vertici i e j se e solo se esiste un vertice t raggiungibile da i e da cui j sia raggiungibile, per cui \(d [t][t]<0\).
Inoltre, quando si utilizza l'algoritmo di Floyd per grafici con cicli negativi, va ricordato che le distanze che sorgono nel processo di lavoro possono andare negativamente, esponenzialmente con ogni fase. Pertanto, dovresti fare attenzione contro l'overflow di numeri interi limitando tutte le distanze dal basso a un certo valore (ad esempio, \(- \infty\)).
Verbalmente, la soluzione può essere descritta come segue:
Dopo che l'algoritmo Floyd-Warshall ha funzionato per il grafico di input, iteriamo su tutte le coppie di vertici \((i,j)\), e per ognuna di queste coppie controlliamo, infinitamente il percorso più breve da i a j è piccolo o no. Per fare questo, iteriamo sul terzo vertice t, e se risulta essere \(d[t][t] < 0\) (cioè si trova nel ciclo di peso negativo), ed è raggiungibile da i e j — allora il percorso \((i,j)\) può essere di lunghezza infinitesimale.