Floyd–Warshall과 음수 사이클

모든 출발점과 모든 도착점의 거리가 필요하면 표를 함께 갱신할 수 있습니다. 목표는 도달 가능성 표와 거리 표의 차이, 없는 간선과 0 비용의 차이를 이해하는 것입니다. Warshall의 중간 정점 단계를 먼저 읽으세요.

개념과 약속

처음 표에는 직접 간선 비용을 넣고 없는 간선은 math.inf로 둡니다. 0은 없는 간선이 아니라 비용 0입니다. 자기 자신까지는 이동 0번의 비용 0을 허용합니다. D[i][j] = min(D[i][j], D[i][k] + D[k][j])로 기존 경로와 k 경유 경로를 비교합니다.

음수 간선도 처리할 수 있지만 음수 사이클이 있으면 그 순환을 반복해 비용을 계속 줄일 수 있어 영향을 받는 쌍에 유한한 최단 비용이 없습니다. 아래 교육용 함수는 계산 뒤 대각선에 음수가 하나라도 있으면 표 전체 반환을 거부합니다. 일부 영향 없는 쌍만 따로 반환하는 고급 정책은 구현하지 않습니다. NaN과 음의 무한대도 입력으로 받지 않습니다.

손으로 상태 추적하기

A→B:4, B→C:-2, A→C:5일 때 B를 중간으로 허용합니다.

음수 간선 -2는 있어도 되돌아가는 순환이 없어 음수 사이클은 없습니다.

직접 실행하기

아래 코드는 이 본문만으로 실행할 수 있습니다. lesson.py로 저장하고 첫 장에서 확인한 Python 명령으로 실행하세요.

import math

def square_size(matrix):
    size = len(matrix)
    if any(len(row) != size for row in matrix):
        raise ValueError("square matrix required")
    return size


def floyd_warshall(weights):
    size = square_size(weights)
    if any(math.isnan(value) or value == -math.inf for row in weights for value in row):
        raise ValueError("NaN and negative infinity are not edge weights")
    distance = [list(row) for row in weights]
    for i in range(size):
        distance[i][i] = min(distance[i][i], 0)
    for k in range(size):
        for i in range(size):
            for j in range(size):
                distance[i][j] = min(distance[i][j], distance[i][k] + distance[k][j])
    if any(distance[i][i] < 0 for i in range(size)):
        raise ValueError("negative cycle: finite shortest paths are not defined")
    return distance


import math
weights = [[0, 4, 5], [math.inf, 0, -2], [math.inf, math.inf, 0]]
for row in floyd_warshall(weights):
    print(row)
try:
    floyd_warshall([[0, -1], [-1, 0]])
except ValueError:
    print("음수 사이클 거부")

실행 결과:

[0, 4, 2]
[inf, 0, -2]
[inf, inf, 0]
음수 사이클 거부

왜 맞고 언제 끝나는가

음수 사이클이 없는 경우 최단 경로는 불필요한 반복을 없애 단순한 정점 순서로 볼 수 있습니다. k를 쓰지 않는 최적 경로 또는 k에서 나눈 두 최적 부분 경로를 비교하면 단계별 최소가 유지됩니다. n단계 뒤 모든 중간 정점을 허용합니다. 음수 대각선은 자기 자신으로 돌아오는 음수 경로의 증거입니다.

비용과 적용 범위

n개 정점에서 O(n³) 시간, O(n²) 추가 공간입니다. 행렬은 정사각형이고 원본 보존용 복사를 만듭니다. 매우 큰 희소 그래프에서 모든 쌍이 필요 없다면 출발점별 Dijkstra 등 다른 방법과 요구 범위를 비교하세요.

스스로 풀어 보기

1. A→B:0, B→C:2, A→C:7이면 최단 A→C는 얼마인가요?
2. A→B:-3, B→A:1에서 A→A를 여러 번 돌면 비용은 어떻게 되나요?

힌트

1. 0 비용도 유효한 간선입니다.
2. 한 바퀴 합은 -2입니다.

해설

1. 0+2=2입니다. 간선 부재를 0으로 표현했다면 이 경우를 잘못 계산합니다.
2. -2,-4,-6처럼 제한 없이 줄어 유한한 최소가 없습니다. 대각선 음수 검사는 그 상황을 탐지합니다.

흔한 오해

Floyd–Warshall과 Warshall은 같은 이름으로 섞어 쓸 수 있는 식이 아닙니다. 전자는 최소 비용의 min·더하기, 후자는 가능성의 or·and입니다.

복습과 다음 연결

다음 DP 상태 설계에서 작은 부분 문제의 답을 표로 보존하는 공통 원리를 확장합니다.