Se um gráfico tiver ciclos de peso negativo, formalmente o algoritmo Floyd-Warshall não é aplicável a tal gráfico.
De fato, para aqueles pares de vértices i ej, entre os quais é impossível entrar em um ciclo de peso negativo, o algoritmo funcionará corretamente.
Para os mesmos pares de vértices para os quais não há resposta (devido à presença de um ciclo negativo no caminho entre eles), o algoritmo de Floyd encontrará algum número (possivelmente fortemente negativo, mas não necessariamente) como resposta. No entanto, o algoritmo de Floyd pode ser aprimorado para lidar com esses pares de vértices de maneira organizada e produzir, por exemplo, \(- \infty\).
Para fazer isso, por exemplo, o seguinte critério "inexistência do caminho" pode ser feito. Portanto, deixe o algoritmo comum do Floyd trabalhar neste gráfico. Então não há caminho mais curto entre os vértices i e j se e somente se houver um vértice t alcançável de i e do qual j é alcançável, para o qual \(d [t][t]<0\).
Além disso, ao usar o algoritmo de Floyd para gráficos com ciclos negativos, deve-se lembrar que as distâncias que surgem no processo de trabalho podem ir de forma negativa, exponencialmente com cada fase. Portanto, você deve tomar cuidado com o estouro de número inteiro, limitando todas as distâncias abaixo para algum valor (por exemplo, \(- \infty\)).
Verbalmente, a solução pode ser descrita da seguinte forma:
Após o algoritmo Floyd-Warshall ter funcionado para o grafo de entrada, vamos iterar sobre todos os pares de vértices \((i,j)\), e para cada um desses pares verificamos, infinitamente o caminho mais curto de i para j é pequeno ou não. Para fazer isso, vamos iterar sobre o terceiro vértice t, e se ele for \(d[t][t] < 0\) (ou seja, encontra-se no ciclo de peso negativo), e é alcançável de i e j — então o caminho \((i,j)\) pode ser de comprimento infinitesimal.