Si un gráfico tiene ciclos de peso negativo, formalmente el algoritmo de Floyd-Warshall no es aplicable a dicho gráfico.
De hecho, para aquellos pares de vértices i y j, entre los cuales es imposible entrar en un ciclo de peso negativo, el algoritmo funcionará correctamente.
Para los mismos pares de vértices para los que no hay respuesta (debido a la presencia de un ciclo negativo en el camino entre ellos), el algoritmo de Floyd encontrará algún número (posiblemente fuertemente negativo, pero no necesariamente) como respuesta. Sin embargo, el algoritmo de Floyd se puede mejorar para manejar dichos pares de vértices de forma ordenada y producir, por ejemplo, \(- \infty\).
Para ello, por ejemplo, se puede realizar el siguiente criterio "inexistencia de la ruta". Entonces, deje que el algoritmo de Floyd habitual funcione en este gráfico. Entonces no hay camino más corto entre los vértices i y j si y solo si hay un vértice t accesible desde i y desde el cual se puede llegar a j, para el cual \(d [t][t]<0\).
Además, al utilizar el algoritmo de Floyd para gráficas con ciclos negativos, se debe recordar que las distancias que surgen en el proceso de trabajo pueden ir negativamente, exponencialmente con cada fase. Por lo tanto, debe tener cuidado contra el desbordamiento de enteros limitando todas las distancias desde abajo a algún valor (por ejemplo, \(- \infty\)).
Verbalmente, la solución se puede describir de la siguiente manera:
Después de que el algoritmo de Floyd-Warshall haya funcionado para el gráfico de entrada, iteremos sobre todos los pares de vértices \((i,j)\), y para cada uno de esos pares comprobamos, infinitamente el camino más corto de i a j es pequeño o no. Para hacer esto, iteremos sobre el tercer vértice t, y si resulta ser \(d[t][t] < 0\) (es decir, se encuentra en el ciclo de peso negativo), y es accesible desde i y j — entonces la ruta \((i,j)\) puede tener una longitud infinitesimal.