그래프에 음의 가중치 주기가 있는 경우 공식적으로 Floyd-Warshall 알고리즘은 이러한 그래프에 적용할 수 없습니다.
실제로 음의 가중치 주기를 입력할 수 없는 정점 i와 j의 쌍에 대해 알고리즘이 올바르게 작동합니다.
답이 없는 동일한 정점 쌍에 대해(그들 사이의 경로에 음의 순환이 존재하기 때문에) Floyd의 알고리즘은 답으로 일부 숫자(매우 음수일 수 있지만 반드시 그런 것은 아님)를 찾습니다. 그러나 Floyd의 알고리즘은 이러한 정점 쌍을 깔끔하게 처리하고 예를 들어 \(- \infty\)를 출력하도록 개선될 수 있습니다.
이를 위해 예를 들어 다음과 같은 기준"경로의 존재하지 않음'을 수행할 수 있습니다. 따라서 일반적인 Floyd 알고리즘이 이 그래프에서 작동하도록 합니다. 그런 다음 i에서 도달할 수 있는 정점 t가 있고 j가 도달할 수 있는 경우에만 정점 i와 j 사이에 최단 경로가 없습니다. \(d [t][t]<0\).
또한 음의 주기가 있는 그래프에 대해 Floyd의 알고리즘을 사용할 때 작업 과정에서 발생하는 거리가 음수로, 각 단계에서 기하급수적으로 갈 수 있음을 기억해야 합니다. 따라서 아래로부터의 모든 거리를 특정 값으로 제한하여 정수 오버플로에 주의해야 합니다(예: \(- \infty\)).
솔루션은 다음과 같이 설명할 수 있습니다.
Floyd-Warshall 알고리즘이 입력 그래프에 대해 작동한 후 모든 정점 쌍에 대해 \((i,j)\), 그리고 이러한 각 쌍에 대해 반복하겠습니다. 무한히 i에서 j까지의 최단 경로가 작은지 아닌지 확인합니다. 이를 위해 세 번째 꼭짓점 t를 반복하고 결과가 \(d[t][t] < 0\) (즉, 음의 가중치 주기에 있음) i 및 j — 그러면 경로는 \((i,j)\) 무한 길이일 수 있습니다.