如果一个图有负权重的循环，那么形式上 Floyd-Warshall 算法不适用于这样的图。
事实上，对于那些顶点对 i j，在它们之间不可能进入一个负权重的循环，该算法将正确工作。
对于没有答案的同一对顶点（由于它们之间的路径上存在负循环），弗洛伊德算法会找到一些数字（可能是强负数，但不一定）作为答案。然而，可以改进 Floyd 算法以巧妙地处理此类顶点对并输出例如 \(- \infty\)。
要做到这一点，例如，可以做到以下 条件 “路径不存在”。因此，让通常的 Floyd 算法在此图上运行。那么在顶点 i 和 j 之间没有最短路径当且仅当存在从 i 可达的顶点 t 并且从该顶点可达 j 时， \(d [t][t]<0\).
此外，当使用 Floyd 算法处理具有负循环的图时，应该记住，在工作过程中出现的距离可能会随着每个阶段呈负增长，呈指数增长。因此，您应该通过将下方的所有距离限制为某个值（例如， \(- \infty\)）来防止整数溢出。
口头上，解决方案可以描述如下：
在 Floyd-Warshall 算法对输入图起作用后，让我们遍历所有顶点对\((i,j)\)，并针对每一对顶点我们检查，无限地从 i 到 j 的最短路径是否小。为此，让我们遍历第三个顶点 t，如果结果是 \(d[t][t] < 0\) （即它位于负权重的循环中），并且它可以从 i and j— 到达那么路径 \((i,j)\) 可以是无限小的长度。