Floyd–Warshall과 음수 사이클

Dijkstra 알고리즘은 출발점 하나에서 다른 모든 정점까지의 최단 거리를 구했습니다. 도시 사이의 거리표처럼 모든 출발점에서 모든 도착점까지의 거리가 필요하다면 출발점마다 Dijkstra 알고리즘을 되풀이해도 되지만, 음수 비용의 간선이 있으면 그마저 쓸 수 없습니다. 이 글에서 다루는 Floyd–Warshall 알고리즘은 Warshall 알고리즘과 똑같은 세 겹의 반복으로 모든 쌍의 최단 거리를 한꺼번에 구하며, 음수 간선도 다룰 수 있습니다. 다만 비용의 합이 음수인 사이클이 있으면 최단 거리라는 말 자체가 성립하지 않는데, 이 알고리즘은 그런 사이클도 찾아낼 수 있습니다.

거리 표에서 시작한다

Floyd–Warshall 알고리즘은 i행 j열에 i에서 j까지의 최단 거리를 적는 표 하나를 채웁니다. 처음에는 직접 이어진 간선의 비용을 적고, 간선이 없는 칸에는 무한대 math.inf를 적습니다. 자기 자신까지는 간선을 하나도 따라가지 않으면 되므로 대각선은 0입니다.

여기서 0과 무한대를 헷갈리지 않아야 합니다. 비용 0인 간선은 공짜로 지나갈 수 있는 실제 간선이고, 무한대는 간선이 없다는 뜻입니다. 인접 행렬에서 간선이 없는 칸을 0으로 적던 습관대로 거리 표를 만들면, 간선이 없는 쌍이 비용 0으로 이어진 것처럼 계산되어 모든 거리가 틀어집니다.

중간 정점을 허용하며 거리를 줄인다

구조는 Warshall 알고리즘과 같습니다. k번째 단계에서는 중간 정점으로 0번부터 k번까지를 허용하고, i에서 j까지의 경로를 k를 거치지 않는 경우와 거치는 경우로 나눕니다. Warshall 알고리즘은 둘 중 하나라도 있는지를 or로 물었지만, 여기서는 둘 중 비용이 작은 쪽을 고릅니다. k를 거치는 경로의 비용은 i에서 k까지의 최단 거리와 k에서 j까지의 최단 거리의 합입니다.

dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

or가 min으로, and가 덧셈으로 바뀐 것입니다. 경로를 이어 붙이려면 두 부분이 모두 있어야 한다는 and의 뜻이 덧셈에도 그대로 들어 있습니다. 어느 한쪽이 무한대이면 합도 무한대가 되어 min에서 선택되지 않기 때문입니다. 간선 A→B가 4, B→C가 -2, A→C가 5일 때 B를 중간 정점으로 허용하는 단계를 보면 다음과 같습니다.

A에서 C로 바로 가는 비용 5보다 B를 거치는 비용 2가 작아서 A→C가 2로 줄었습니다. 이 그래프에는 음수 간선 -2가 있지만, 출발점으로 되돌아오는 사이클이 없으므로 문제가 없습니다.

코드로 옮기기와 경로 복원

거리뿐 아니라 경로도 알고 싶다면, i에서 j로 가는 최단 경로에서 i 다음에 가는 정점을 nxt[i][j]에 기록해 둡니다. 처음에는 직접 간선이 있으면 j 자신이 다음 정점이고, 간선이 없으면 None입니다. k를 거치는 경로가 더 싸서 거리를 고칠 때는, i에서 j로 가는 경로가 i에서 k로 가는 경로로 시작하므로 nxt[i][j]를 nxt[i][k]로 바꿉니다. 경로를 복원할 때는 i에서 시작해 nxt를 따라 j에 닿을 때까지 이동하면 됩니다.

아래 예는 Dijkstra 알고리즘의 그래프에서 간선이 없는 정점 E를 빼고, 비용 -1인 간선 D→A를 더한 것입니다.

import math

INF = math.inf


def floyd_warshall(weights):
    n = len(weights)
    dist = [list(row) for row in weights]
    nxt = [[j if weights[i][j] != INF else None for j in range(n)] for i in range(n)]
    for i in range(n):
        dist[i][i] = min(dist[i][i], 0)
        nxt[i][i] = i
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
                    nxt[i][j] = nxt[i][k]
    if any(dist[i][i] < 0 for i in range(n)):
        raise ValueError("음수 사이클이 있어 최단 거리가 정해지지 않습니다")
    return dist, nxt


def restore_path(nxt, i, j):
    if nxt[i][j] is None:
        return []
    path = [i]
    while i != j:
        i = nxt[i][j]
        path.append(i)
    return path


names = ["A", "B", "C", "D"]
weights = [
    [0, 4, 1, INF],
    [INF, 0, INF, 1],
    [INF, 2, 0, 5],
    [-1, INF, INF, 0],
]
dist, nxt = floyd_warshall(weights)
for name, row in zip(names, dist):
    print(name, row)
print([names[v] for v in restore_path(nxt, 0, 3)])
print([names[v] for v in restore_path(nxt, 3, 1)])
try:
    floyd_warshall([[0, -3], [1, 0]])
except ValueError as error:
    print("오류:", error)

A [0, 3, 1, 4]
B [0, 0, 1, 1]
C [2, 2, 0, 3]
D [-1, 2, 0, 0]
['A', 'C', 'B', 'D']
['D', 'A', 'C', 'B']
오류: 음수 사이클이 있어 최단 거리가 정해지지 않습니다

네 줄의 표 다음에는 A에서 D까지와 D에서 B까지의 경로가 나옵니다. 마지막 줄의 오류는 뒤에서 설명할 음수 사이클이 있는 그래프를 넣은 결과입니다. A행은 Dijkstra 알고리즘으로 구한 거리 0, 3, 1, 4와 같습니다. 새로 생긴 정보는 다른 행들입니다. B에서 A로는 직접 간선이 없지만 B→D→A로 1 + (-1) = 0에 갈 수 있고, D에서 B로는 D→A→C→B로 -1 + 1 + 2 = 2에 갈 수 있습니다. 음수 간선 D→A가 있어도 A→C→B→D→A 사이클의 비용은 1 + 2 + 1 + (-1) = 3으로 양수라서 최단 거리가 잘 정해집니다.

음수 사이클이 있으면

비용의 합이 음수인 사이클을 음수 사이클(negative cycle)이라고 합니다. 간선 A→B가 -3, B→A가 1이면 A→B→A를 한 바퀴 돌 때마다 비용이 -2씩 줄어듭니다. 두 바퀴면 -4, 세 바퀴면 -6으로 한없이 줄어들므로, A에서 A로, 또 이 사이클을 지나는 다른 쌍들 사이에서 "가장 작은 비용"이 존재하지 않습니다. 최단 거리라는 답 자체가 없는 것입니다.

Floyd–Warshall 알고리즘은 이런 사이클을 대각선으로 알아챕니다. 대각선은 0에서 시작하는데, 계산이 끝난 뒤 dist[i][i]가 음수라면 i에서 출발해 i로 돌아오는 비용이 음수인 경로를 찾았다는 뜻이고, 그 경로에는 음수 사이클이 들어 있습니다. 반대로 i를 지나는 음수 사이클이 있으면 알고리즘이 그 사이클의 정점들을 중간 정점으로 허용하는 동안 dist[i][i]가 음수로 내려갑니다. 그래서 위의 함수는 대각선에 음수가 하나라도 있으면 표를 돌려주지 않고 오류를 냅니다. 앞의 코드 마지막 부분에서 간선 A→B가 -3, B→A가 1인 그래프를 넣었을 때 오류가 난 것이 이 때문입니다.

음수 사이클이 있어도 그 사이클과 상관없는 쌍의 최단 거리는 정해질 수 있습니다. 그런 쌍만 골라서 돌려주는 방법도 있지만, 이 글의 함수는 단순하게 표 전체를 거절합니다.

왜 맞는가

음수 사이클이 없다면, 최단 경로는 같은 정점을 두 번 지나지 않는 경로 가운데에서 찾을 수 있습니다. 경로가 어떤 정점을 두 번 지나면 그 사이의 사이클 부분을 잘라 낼 수 있고, 그 사이클의 비용이 음수가 아니므로 잘라 내도 비용이 늘지 않기 때문입니다. 이 사실 덕분에 Warshall 알고리즘에서와 같은 귀납법을 쓸 수 있습니다. k번 단계가 끝나면 dist[i][j]는 중간 정점으로 0번부터 k번까지만 거치는 경로 가운데 가장 싼 비용입니다. 그런 최단 경로가 k를 거치지 않으면 이전 단계의 값이고, k를 한 번 거치면 i에서 k까지와 k에서 j까지의 두 부분으로 나뉘며 각 부분은 k보다 앞선 정점만 거치는 최단 경로입니다. 최단 경로의 부분 경로가 다시 최단 경로라는 이 성질은 다음 장의 동적 계획법에서 핵심으로 다룹니다.

경로 복원도 이 갱신과 함께 맞습니다. dist[i][j]를 k를 거치는 값으로 고칠 때 nxt[i][j]를 nxt[i][k]로 바꾸므로, nxt[i][j]는 늘 지금 기록된 최단 경로에서 i 다음의 정점을 가리킵니다.

비용과 다른 방법과의 비교

세 겹의 반복으로 시간은 O(n³), 거리 표와 다음 정점 표로 공간은 O(n²)입니다. 간선 비용이 모두 음수가 아니라면 출발점마다 힙을 쓴 Dijkstra 알고리즘을 돌려 O(V(V + E) log V)에 같은 표를 얻을 수 있고, 간선이 적은 큰 그래프에서는 이쪽이 훨씬 빠릅니다. Floyd–Warshall 알고리즘은 코드가 짧고, 음수 간선을 다룰 수 있으며, 정점이 수백 개 정도이고 간선이 많은 그래프에서 쓰기 좋습니다.

정리

• Floyd–Warshall 알고리즘은 중간 정점을 하나씩 허용하며 dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])로 모든 정점 쌍의 최단 거리를 구합니다. Warshall 알고리즘의 or와 and를 min과 덧셈으로 바꾼 것입니다.
• 거리 표는 직접 간선의 비용, 간선이 없으면 무한대, 대각선은 0으로 시작합니다. 비용 0인 간선과 간선이 없는 것은 다릅니다.
• 거리를 고칠 때 다음 정점 표를 nxt[i][j] = nxt[i][k]로 함께 고치면 최단 경로를 복원할 수 있습니다.
• 음수 간선은 다룰 수 있지만, 음수 사이클이 있으면 최단 거리가 정해지지 않습니다. 계산 뒤 대각선에 음수가 있으면 음수 사이클이 있는 것입니다.
• 시간은 O(n³), 공간은 O(n²)이며, 음수 간선이 없고 간선이 적은 그래프에서는 출발점마다 Dijkstra 알고리즘을 쓰는 편이 빠를 수 있습니다.

연습 문제

1. 비용 0인 간선

간선 A→B가 0, B→C가 2, A→C가 7일 때 A에서 C까지의 최단 거리는 얼마인가요? 거리 표를 만들 때 간선이 없는 칸을 0으로 적으면 어떤 문제가 생기나요?

2. 음수 사이클을 여러 번 돌면

간선 A→B가 -3, B→A가 1일 때, A에서 출발해 A로 돌아오는 경로의 비용은 사이클을 한 바퀴, 두 바퀴, 세 바퀴 돌 때 각각 얼마인가요? 이 그래프를 본문의 함수에 넣으면 어떻게 되나요?

3. 경로 복원 따라가기

본문의 4정점 예제에서 restore_path(nxt, 3, 1), 곧 D에서 B까지의 경로가 ['D', 'A', 'C', 'B']로 나오는 과정을 nxt 표로 설명하세요.

다음 장의 DP 상태·점화식·계산 순서에서는 Floyd–Warshall 알고리즘처럼 작은 문제의 답을 표에 저장해 두고 큰 문제의 답을 만드는 동적 계획법을 본격적으로 다룹니다.