Floyd-Warshall은 모든 출발점과 도착점 쌍의 최단 거리를 하나의 n×n 행렬로 계산하는 동적 계획법입니다. 핵심 상태는 “지금까지 허용한 중간 정점 집합이 무엇인가”입니다. 정점 k를 새로 중간 정점으로 허용할 때 i→j 경로가 기존 경로보다 짧아지는지 i→k→j로 비교합니다.
이 알고리즘은 단일 source의 경로만 필요한 문제와 목적이 다릅니다. 그래프가 작거나 조밀하고 모든 쌍의 결과가 필요하면 구현이 간결하지만, 정점 수가 커지면 시간 O(n³)와 거리 행렬 공간 O(n²) 자체가 주된 비용입니다. 희소 입력이라고 해서 삼중 루프와 행렬 저장이 자동으로 희소해지는 것은 아닙니다.
전쌍 행렬과 초기 상태
행렬 D[i][j]는 현재 허용된 중간 정점 집합을 거치는 최단 비용을 저장합니다. 초기 단계에서는 중간 정점을 허용하지 않으므로 직접 간선이 있으면 그 비용, i==j이면 0, 연결이 없으면 INF로 둡니다. 같은 방향 사이에 여러 간선이 있으면 직접 간선 중 최소 비용을 초기값으로 취해야 합니다.
방향 그래프에서 i→j와 j→i는 서로 다른 셀입니다. 무방향 그래프라면 양방향 셀을 함께 초기화하되, 표현을 바꾸는 과정에서 간선의 방향이나 평행 간선 정책을 잃지 않아야 합니다. INF는 실제 숫자가 아니므로 아직 연결되지 않은 두 부분경로를 더하는 연산을 건너뛰어야 합니다.
예를 들어 정점 1,2,3,4와 직접 간선 1→2=2, 2→4=3, 1→4=10, 1→3=8, 3→4=1이 있으면 초기 D[1][4]=10입니다. 중간 정점 2를 허용하면 D[1][2]+D[2][4]=5로 낮아지고, 정점 3을 허용해도 8+1=9이므로 5가 유지됩니다.
중간 정점 집합의 점화식
정점을 어떤 순서로 번호 매기고 1..k까지만 중간에 등장할 수 있다고 정의합니다. 그러면 D_k[i][j]는 다음 두 경우의 최솟값입니다.
- 정점
k를 사용하지 않는 최단 경로:D_{k-1}[i][j] k를 적어도 한 번 사용하는 최단 경로:D_{k-1}[i][k] + D_{k-1}[k][j]
경로 중간에서 k를 여러 번 방문하는 경우가 유한 최단 경로에서 의미 있게 반복될 수 있으려면 음수 cycle 문제가 먼저 다뤄져야 합니다. 음수 cycle이 없다면 단순화한 최단 경로를 기준으로 k를 한 번의 분할점처럼 생각할 수 있고, 점화식은 min으로 표현됩니다.
그림을 글로 읽기
- D[i][j]: 기존 경로
- D[i][k]: 첫 구간
- D[k][j]: 둘째 구간
- min 비교: 새 D[i][j]
- D[i][j] → min 비교: 그대로 유지
- D[i][k] → min 비교: i→k 비용
- D[k][j] → min 비교: k→j 비용
행렬을 in-place로 갱신할 때도 바깥 루프가 k여야 합니다. 고정된 k에서 D[i][k]와 D[k][j]가 같은 단계의 값으로 사용되고, 자기 자신을 중간에 다시 허용해도 음수 cycle이 없는 한 의미가 유지됩니다. i, j, k의 순서를 무심코 바꾸면 중간 정점 집합 불변식이 깨질 수 있습니다.
숫자 상태의 단계 추적
다음 작은 그래프에서 정점 번호 1부터 4까지 차례로 허용하겠습니다.
| 단계 | D[1][4] |
개선 근거 | 해석 |
|---|---|---|---|
| 초기 | 10 | 직접 간선 | 중간 정점 없음 |
k=1 |
10 | D[1][1]+D[1][4] |
새 경로 없음 |
k=2 |
5 | D[1][2]=2, D[2][4]=3 |
1→2→4 |
k=3 |
5 | 8+1=9 |
기존 5가 더 짧음 |
k=4 |
5 | 목표가 중간으로 재사용되어도 변화 없음 | 최종 |
다른 셀도 같은 방식으로 갱신합니다. D[1][3]이 직접 8이지만 1→2→4와 관련이 없으므로 3으로 내려가지 않습니다. 경로가 존재하는지와 비용이 낮은지는 셀별로 분리해 읽어야 합니다.
INF + finite를 계산하지 않는 것도 상태 추적의 일부입니다. D[i][k]=INF인데 D[k][j]가 음수라면 표식에 음수를 더해 유한 값처럼 만드는 버그가 생깁니다. 두 값 모두 유한할 때만 후보를 만들고, 큰 정수 비용이라면 checked addition으로 범위를 확인합니다.
In-place 갱신과 경로 복원
거리만 필요하다면 for k, for i, for j 순서로 D[i][j] = min(D[i][j], D[i][k] + D[k][j])를 수행할 수 있습니다. 경로 정점을 복원해야 한다면 거리와 함께 next[i][j] 또는 중간 정점 정보를 갱신해야 합니다. D[i][j]가 i→k→j로 개선될 때 next[i][j]를 next[i][k]로 설정하면 이후 next를 따라 실제 경로를 나열할 수 있습니다.
거리 행렬만 저장한 뒤 나중에 임의의 predecessor를 추정할 수는 없습니다. 동률 경로가 여러 개일 수 있고, negative cycle이 있으면 “최단 경로” 자체가 없을 수 있기 때문입니다. 경로 복원 계약에는 동률에서 어느 경로를 택할지, source와 target이 같은 경우를 어떻게 출력할지, cycle 영향이 있는 쌍을 거절할지를 포함해야 합니다.
경로 복원 반복은 잘못된 next 갱신이나 negative cycle 때문에 무한 루프가 될 수 있습니다. 최대 n번 정점을 넘게 따라가면 invalid path metadata 또는 cycle 상태로 처리하는 방어가 필요합니다. 경로 결과를 반환할 때 거리 갱신과 metadata 갱신이 서로 다른 snapshot을 보지 않도록 같은 분기에서 함께 수정합니다.
음수 간선과 음수 대각선
Floyd-Warshall은 음수 간선을 허용하지만, 음수 cycle이 있으면 모든 쌍의 최단 거리가 자동으로 유한하다는 뜻은 아닙니다. 계산 후 D[v][v] < 0인 정점 v가 하나라도 있으면 v가 음수 cycle에 속하거나 v가 접근 가능한 cycle과 돌아오는 경로를 통해 자기 자신을 음수 비용으로 재방문할 수 있다는 의미입니다. 대각선의 음수는 cycle 존재를 알려 주는 신호이지 모든 셀을 -INF로 만드는 명령이 아닙니다.
source s에서 음수 cycle 정점 v로 갈 수 있고 v에서 target t로 갈 수 있을 때만 s→t 쌍은 cycle을 반복해 비용을 무한히 낮출 수 있습니다. 예를 들어 A가 음수 cycle에 속하지만 B로 나가는 경로가 없으면 S→A는 영향 대상이어도 S→B는 그 cycle의 출구가 없어서 같은 이유로 -INF가 되지 않습니다.
영향을 표시하려면 음수 대각선 후보 v를 찾은 뒤 모든 i,j에 대해 D[i][v] != INF이고 D[v][j] != INF인지 확인하여 해당 셀을 NEGATIVE_CYCLE_REACHABLE 상태로 바꿀 수 있습니다. 이 후처리는 방향성을 보존해야 하며, 단순히 diagonal 하나를 발견했다는 이유로 전체 행렬을 오염시키면 안 됩니다.
알고리즘 선택과 희소 그래프
n=100000인 희소 그래프는 Floyd-Warshall의 대표적인 부적합 사례입니다. n³번 비교는 실행 규모가 지나치게 크고 n² 거리 행렬도 저장만으로 큰 비용이 듭니다. 출발점이 하나라면 비음수 간선에는 Dijkstra, 음수 간선과 cycle 탐지가 필요하면 Bellman-Ford를 검토할 수 있습니다. 여러 출발점이 꼭 필요하다면 각 source 반복이나 Johnson 계열 등 입력 조건에 맞는 대안을 비교해야 합니다.
all-pairs 요구가 있다고 해서 무조건 Floyd-Warshall을 선택하지는 않습니다. 정점 수, 간선 밀도, 음수 간선 여부, 질의가 모든 쌍인지 일부 source인지, 거리 행렬을 동시에 메모리에 둘 필요가 있는지, 경로 복원이 필요한지를 먼저 정합니다. 희소 adjacency list를 입력으로 써도 Floyd-Warshall의 내부 상태는 기본적으로 조밀 행렬이므로 입력 표현만 바꿔 O(n³)를 없앨 수 없습니다.
반대로 수백 개 이하의 정점에서 모든 쌍을 반복 질의하고 행렬 접근의 단순성이 중요하다면 Floyd-Warshall이 적절할 수 있습니다. 정적 행렬을 여러 번 읽는 서비스라면 계산 이후 query가 O(1)인 점도 선택 이유가 됩니다. 대신 변경이 자주 발생하면 전체 재계산 비용이 곧바로 드러납니다.
구현 계약과 비용
의사코드는 다음과 같이 표현할 수 있습니다.
D[i][j] = INF for every i, j
D[i][i] = 0
for each edge (u, v, w):
D[u][v] = min(D[u][v], w)
for k in vertices in fixed order:
for i in vertices:
if D[i][k] == INF:
continue
for j in vertices:
if D[k][j] == INF:
continue
candidate = checked_add(D[i][k], D[k][j])
D[i][j] = min(D[i][j], candidate)
negativeCycleVertices = [v where D[v][v] < 0]
여기서 D[i][i]=0은 음수 cycle이 없다는 초기 가정의 기본 경로입니다. 자기 간선이 음수인 입력은 반복 전에 이미 cycle 후보가 됩니다. checked_add 실패는 음수 cycle과 다른 수치 오류이므로 별도 상태로 반환합니다.
시간은 O(n³), 거리 행렬 공간은 O(n²)입니다. next 행렬이나 predecessor를 추가하면 또 O(n²) 공간이 필요합니다. in-place 갱신은 이전 모든 단계의 행렬을 보존하지 않아도 되는 대신, k 순서와 동시에 읽는 값의 의미를 코드 리뷰에서 확인해야 합니다. 행렬이 크다면 캐시 블로킹 같은 구현 최적화가 가능하지만 점근 복잡도와 negative cycle 의미는 바뀌지 않습니다.
검증과 참고 범위
검증에는 직접 경로와 우회 경로가 있는 4정점 예제, 도달하지 않는 정점, 음수 간선만 있는 그래프, 음수 대각선이 하나인 방향 그래프, cycle에서 target으로 나가는 경로가 없는 경우, 평행 간선과 자기 간선을 포함합니다. 각 k 단계에서 허용된 중간 정점이 실제 경로에 포함되는지 상태 표로 확인하고, Dijkstra나 작은 완전 탐색 결과와 음수 cycle이 없는 입력에서 대조합니다.
이 문서의 점화식, in-place k 순서, 음수 대각선의 cycle 의미, O(n³) 비용은 입력 계약에 지정된 CP-algorithms Floyd-Warshall 참고 항목 및 저장소의 dynamic-programming 설명을 대조해 작성했습니다. 해당 참고 페이지는 알고리즘 교육 자료이므로 사용 언어의 INF 타입, path API, overflow 동작을 보장하지 않습니다. 실행하지 않은 코드는 설명용 계산과 예상 상태로 표시했으며, 특정 런타임에서 성공했다고 주장하지 않습니다.
참고 경로
위 링크는 개념별 참고 경로이며, 본문에서 명시한 확인 범위와 미확인 구현 조건을 함께 적용합니다.