グラフに負の重みのサイクルがある場合、正式にはフロイド-ウォーシャル アルゴリズムはそのようなグラフには適用できません。
実際、頂点 i j と頂点 j のペアでは、その間で負の重みのサイクルに入ることが不可能であり、アルゴリズムは正しく機能します。
答えのない同じ頂点のペア (それらの間のパス上に負のサイクルが存在するため) については、フロイドのアルゴリズムは答えとして何らかの数値 (おそらく強い負の数ですが、必ずしもそうではありません) を見つけます。ただし、Floyd のアルゴリズムを改良して、このような頂点のペアを適切に処理して、\(- \infty\) などの出力を行うことができます。
これを行うには、たとえば、次の基準 「パスが存在しない」を実行できます。そこで、このグラフに対して通常の Floyd アルゴリズムを実行してみましょう。この場合、頂点 i と j の間に最短経路は存在せず、 i から到達可能な頂点 t が存在し、そこから j が到達可能な場合にのみ存在します。その場合、 \(d [t][t]<0\)。
さらに、負のサイクルを持つグラフにフロイドのアルゴリズムを使用する場合、作業の過程で生じる距離は各段階で負に、指数関数的に増加する可能性があることに留意する必要があります。したがって、以下からのすべての距離を特定の値 (例: \(- \infty\)) に制限することで、整数のオーバーフローに注意する必要があります。
口頭では、解決策は次のように説明できます。
入力グラフに対して Floyd-Warshall アルゴリズムが機能した後、頂点のすべてのペア\((i,j)\)を反復処理して、そのようなペアごとにi から j までの無限の最短経路が小さいかどうかを確認します。これを行うには、3 番目の頂点 t を反復処理して、それが\(d[t][t] < 0\)であることが判明した場合、 (つまり、負の重みのサイクル内にあります)、i および j— から到達可能です。この場合、パス\((i,j)\) の長さは無限小でもかまいません。