플로이드 알고리즘

플로이드 알고리즘은 여러 곳 사이의 가장 짧은 거리를 모든 짝에 대해 한꺼번에 구해 줍니다. 곳과 곳 사이의 거리를 적은 표 하나를 계속 고쳐 씁니다. 들러 가도 되는 곳을 하나씩 늘려 가며 표의 값을 더 짧은 거리로 바꿉니다. 마지막에 남은 표가 답입니다.

상세

이 절은 플로이드 알고리즘이 무엇을 받아 무엇을 내는지부터 봅니다. 그다음 노드 네 개짜리 작은 그래프 하나로 표가 어떻게 바뀌는지 끝까지 따라갑니다. 답이 왜 맞는지, 코드로 어떻게 옮기는지, 얼마나 걸리는지, 언제 쓰는지는 그 뒤에 차례로 봅니다.

이름은 이 절차를 내놓은 미국의 컴퓨터 과학자 로버트 플로이드(Robert Floyd)에게서 왔습니다. 같은 무렵 스티븐 워셜(Stephen Warshall)이 같은 모양의 절차로 「갈 수 있나 없나」를 구했습니다. 그래서 플로이드-워셜 알고리즘이라고도 부릅니다.

플로이드라는 이름이 붙은 절차는 하나 더 있습니다. 연결 리스트에 고리가 있는지 찾는 플로이드 순환 탐지 알고리즘입니다. 이 편은 그 절차가 아니라 최단 거리를 구하는 절차를 다룹니다.

넣는 것과 나오는 것

넣는 것은 가중치가 붙은 그래프 하나입니다. 나오는 것은 모든 노드 짝 사이의 가장 짧은 거리를 적은 표입니다. 아래에서 이 두 문장에 나온 낱말을 하나씩 풀고, 나오는 표의 모양을 봅니다.

플로이드 알고리즘은 그래프 위에서 돕니다. 그래프는 점과 그 점들을 잇는 선으로 관계를 나타낸 구조입니다. 도시와 도로, 서버와 회선처럼 무엇과 무엇이 이어져 있는지를 담습니다.

점을 노드라고 합니다. 정점이라고도 부릅니다. 도시와 도로로 치면 도시 하나가 노드입니다.

점을 잇는 선은 간선이라고 합니다. 도시와 도로로 치면 도로 하나가 간선입니다.

이 편의 간선에는 방향이 있습니다. 화살표 방향으로만 지나갈 수 있습니다. 반대로 가려면 반대 방향 간선이 따로 있어야 합니다. 이런 그래프를 방향 그래프라고 합니다.

간선마다 숫자가 하나씩 붙습니다. 이 숫자가 가중치입니다. 그 간선을 지나는 비용을 뜻합니다. 도로라면 지나는 데 걸리는 분이, 네트워크라면 회선을 건너는 지연 시간이 가중치가 됩니다.

한 길의 거리는 그 길이 지나는 간선들의 가중치를 모두 더한 값입니다. 두 노드 사이에서 거리가 가장 작은 길을 최단 경로라고 합니다.

나오는 표로 돌아갑니다. 노드가 V 개면 V 행 V 열짜리 표입니다. i 행 j 열 칸에 i 에서 j 까지의 최단 거리가 들어갑니다.

다익스트라 알고리즘은 출발점 하나에서 다른 모든 노드까지의 최단 거리를 구합니다. 플로이드 알고리즘은 모든 노드를 출발점으로 삼은 답을 한 번에 냅니다. 이 문제를 모든 쌍 최단 경로 문제라고 부릅니다.

가중치에는 음수가 있어도 됩니다. 조건은 하나입니다. 한 바퀴 돌아 출발한 노드로 돌아오는 길의 합이 음수이면 안 됩니다.

이렇게 출발한 노드로 돌아오는 길을 사이클이라고 합니다. A → B → A 처럼 한 바퀴 도는 길입니다. 가중치 합이 음수인 사이클은 음수 사이클이라고 부릅니다. 음수 사이클이 왜 안 되는지는 아래 「음수 사이클」 소절에서 봅니다.

출발 표

이 소절은 알고리즘이 처음 받아 드는 표를 봅니다. 예로 쓸 그래프는 노드 A · B · C · D 넷과 간선 일곱 개입니다.

flowchart TD
    A((A)) -->|3| B((B))
    A -->|7| D((D))
    B -->|8| A
    B -->|2| C((C))
    C -->|5| A
    C -->|1| D
    D -->|2| A

화살표 옆 숫자가 가중치입니다. A 에서 B 로는 3 이지만 B 에서 A 로 바로 가는 간선은 8 입니다. 방향에 따라 비용이 다를 수 있습니다.

이 그래프를 표로 옮깁니다. 행이 출발 노드, 열이 도착 노드입니다.

간선이 있으면 그 가중치를 적습니다. 간선이 없으면 무한대(∞)를 적습니다. 자기 자신까지의 거리는 0 입니다.

그래프를 노드 수만큼의 행과 열로 담는 이런 표를 인접 행렬이라고 합니다. 두 노드가 이어져 있는지를 칸 하나만 보고 답할 수 있어서, 칸을 계속 고쳐 쓰는 이 절차와 잘 맞습니다.

이 표는 간선 하나로 가는 길만 압니다. B 에서 D 로는 간선이 없어서 ∞ 입니다. B → C → D 로 가면 2 더하기 1 로 3 인데도 그렇습니다. 알고리즘이 할 일은 이런 돌아가는 길을 찾아 칸을 채우는 것입니다.

들를 노드를 하나씩 늘리는 절차

이 소절은 절차 전체를 봅니다. 절차는 노드를 하나씩 차례로 골라 표 전체를 한 번 훑는 일을 노드 수만큼 되풀이합니다. 지금 고른 노드를 k 라고 부릅니다.

k 를 골랐으면 표의 모든 칸 (i, j) 에 같은 질문을 합니다. 「i 에서 k 로 간 다음 k 에서 j 로 가면 지금 적힌 값보다 짧아지나」입니다. 짧아지면 그 칸을 두 거리의 합으로 고쳐 적습니다.

거리 표를 dist 라고 부르면 한 칸에서 하는 일은 한 줄입니다. dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) 입니다. 더 짧은 길을 찾았을 때 표의 값을 낮춰 적는 이 동작을 완화라고 부릅니다.

A 부터 D 까지 k 로 골라 앞의 표에 절차를 돌립니다. 아래 표는 k 마다 값이 바뀐 칸만 적었습니다. 칸은 (출발, 도착) 으로 적습니다. (B, D) 는 B 행 D 열, 곧 B 에서 D 까지의 거리를 적는 칸입니다.

k 가 A 일 때 (D, B) 가 5 가 됐습니다. D → A → B 로 2 더하기 3 입니다. 같은 때 (B, D) 는 15 가 됐습니다. B → A → D 로 8 더하기 7 입니다.

(B, D) 의 15 는 최종 답이 아닙니다. k 가 C 일 때 B → C → D 가 드러나 3 으로 줄었습니다. (B, A) 는 8 에서 7 로, 다시 5 로 두 번 줄었습니다. 들러도 되는 노드가 늘 때마다 더 짧은 길이 드러나기 때문입니다.

네 노드를 모두 거쳐 본 뒤의 표는 아래와 같습니다. 이것이 답입니다.

(B, A) 의 5 는 B → C → D → A 로 2, 1, 2 를 더한 값입니다. 간선을 세 개 지나는 길도 이렇게 찾아졌습니다. 처음 표에서 ∞ 이던 칸이 모두 채워졌습니다. 이 그래프에서는 어느 노드에서든 다른 모든 노드로 갈 수 있다는 뜻입니다.

절차가 맞는 답을 내는 까닭

이 소절은 표를 몇 번 훑기만 하는 절차가 왜 최단 거리를 빠짐없이 찾는지 봅니다. 열쇠는 k 까지 거쳐 본 뒤의 표가 무엇을 담고 있느냐입니다.

먼저 낱말 하나를 정합니다. 길의 「중간 노드」는 출발 노드와 도착 노드를 뺀, 길 가운데에서 들르는 노드입니다. B → C → D 의 중간 노드는 C 하나입니다.

A 까지 거쳐 본 뒤의 표는 「중간 노드로 A 만 쓸 수 있는 길」 가운데 최단 거리를 담습니다. B 까지 거쳐 본 뒤에는 「중간 노드로 A 와 B 만 쓸 수 있는 길」의 최단 거리를 담습니다. D 까지 거쳐 보면 모든 노드를 중간 노드로 쓸 수 있으므로 표가 진짜 최단 거리가 됩니다.

아래에서 「k 앞 노드」는 k 보다 먼저 골라 거쳐 본 노드들을 말합니다. k 자신은 들어가지 않습니다. k 가 C 이면 k 앞 노드는 A 와 B 입니다.

k 를 새로 허락할 때 할 일을 봅니다. i 에서 j 로 가는 가장 짧은 길은 k 를 들르거나 안 들르거나 둘 중 하나입니다.

flowchart TD
    I(("i")) -->|"k 앞 노드만 들름 · dist[i][k]"| K(("k"))
    K -->|"k 앞 노드만 들름 · dist[k][j]"| J(("j"))
    I -.->|"k 를 안 들름 · 지금의 dist[i][j]"| J

k 를 안 들르는 길이면 그 최단 거리는 이미 표에 있습니다. k 를 들르는 길이면 k 에서 잘라 두 도막으로 나눕니다. i 에서 k 까지와 k 에서 j 까지입니다.

두 도막의 최단 거리도 이미 표에 있으려면, 두 도막 모두 k 를 다시 들르지 않는다는 보장이 필요합니다. 그래야 두 도막이 k 앞 노드만 중간 노드로 쓰는 길이 됩니다.

가장 짧은 길은 k 를 두 번 들를 까닭이 없습니다. 두 번 들르면 그 사이가 k 에서 k 로 돌아오는 사이클입니다. 음수 사이클이 아니면 그 사이클을 빼는 편이 짧거나 같습니다.

그래서 두 도막의 최단 거리도 이미 표에 있습니다. 지금 칸의 값과 두 도막의 합 가운데 작은 쪽이 새 답입니다. 완화가 하는 일이 이 비교입니다.

최단 경로를 두 도막으로 자르면 각 도막도 그 두 끝 사이의 최단 경로입니다. 이 성질을 최적 부분 구조라고 합니다. 위의 두 도막 논리가 이 성질에 기댑니다.

작은 문제의 답을 표에 적어 두고, 그 답을 조합해 큰 문제의 답을 만드는 방법을 동적 계획법이라고 합니다. 플로이드 알고리즘에서 작은 문제는 「k 앞 노드만 들르는 최단 거리」입니다. 큰 문제는 「k 까지 들르는 최단 거리」입니다. 표 한 장이 그 답들을 차례로 담습니다.

파이썬으로 옮긴 코드

이 소절은 앞의 그래프를 파이썬 코드로 옮겨 돌려 봅니다. 먼저 출발 표를 2차원 리스트로 적습니다. 행과 열의 번호 0 · 1 · 2 · 3 이 A · B · C · D 입니다.

INF = float("inf")

dist = [
    [0,   3,   INF, 7  ],
    [8,   0,   2,   INF],
    [5,   INF, 0,   1  ],
    [2,   INF, INF, 0  ],
]

INF 는 파이썬의 실수 무한대입니다. 무한대에 어떤 수를 더해도 무한대라서 이어지지 않은 칸을 그대로 나타냅니다.

함수는 이 표를 받아 칸을 직접 고쳐 씁니다. 반복문 세 겹이 전부입니다.

def floyd(dist):
    n = len(dist)
    for k in range(n):
        for i in range(n):
            for j in range(n):
                via = dist[i][k] + dist[k][j]
                if via < dist[i][j]:
                    dist[i][j] = via
    return dist

via 는 k 를 거쳐 가는 길의 거리입니다. 그 값이 지금 칸보다 작으면 칸을 고칩니다. 돌린 결과를 몇 칸 꺼내 보면 앞 소절의 마지막 표와 같습니다.

d = floyd(dist)
d[1][0]   # 5 · (B, A)
d[2][1]   # 6 · (C, B)
d[0][3]   # 6 · (A, D)

(B, A) 는 B → C → D → A 의 5, (C, B) 는 C → D → A → B 의 6 입니다.

반복문 순서와 무한대 값

코드를 옮길 때 틀리기 쉬운 곳이 셋 있습니다. 반복문의 순서, 표를 한 장만 두고 덮어쓰는 것, 무한대 값입니다.

k 반복문은 반드시 맨 바깥에 둡니다. k 를 안쪽에 두면 칸 (i, j) 를 고칠 때 dist[i][k] 가 아직 앞 노드들을 다 거쳐 보지 않은 값일 수 있습니다. 그러면 앞 소절의 「k 까지 거쳐 본 표」라는 약속이 깨지고 답이 틀립니다.

위 코드는 표를 한 장만 두고 칸을 그 자리에서 덮어씁니다. 그러면 걱정이 하나 생깁니다. 같은 k 차례 안에서 먼저 고친 칸을 뒤 칸의 계산이 읽을 수 있습니다.

칸 (i, j) 를 계산할 때 읽는 다른 칸은 dist[i][k] 와 dist[k][j] 뿐입니다. 곧 k 열과 k 행입니다. 이 두 줄은 k 차례 동안 바뀌지 않습니다.

예를 들어 dist[i][k] 를 k 를 거쳐 고치면 dist[i][k] + dist[k][k] 가 됩니다. 음수 사이클이 없으면 dist[k][k] 가 0 이라 값이 같습니다. dist[k][j] 도 같은 까닭으로 그대로입니다.

k 행과 k 열이 그대로이니, 먼저 고친 칸을 읽어도 계산 결과는 같습니다. 그래서 표를 한 장만 써도 됩니다.

자바의 int 처럼 무한대가 없는 정수 타입에서는 아주 큰 값을 무한대 대신 씁니다. 이 값끼리 더하면 정수 오버플로가 나서 값이 음수로 뒤집힙니다. 그러면 없는 길이 가장 짧은 길로 뽑힙니다. 더하기 전에 한쪽이 무한대인지 먼저 보거나, 두 번 더해도 넘치지 않을 만큼만 큰 값을 무한대로 씁니다.

걸리는 시간과 메모리

이 소절은 그래프가 커질 때 비용이 어떻게 늘어나는지 봅니다. 노드 수는 V, 간선 수는 E 로 적습니다.

이런 늘어남은 빅오 표기법으로 적습니다. 빅오 표기법은 입력이 커질 때 비용이 어떤 모양으로 따라 커지는지를 적는 약속입니다. O(V³) 은 V 의 세제곱에 비례한다는 뜻입니다.

반복문 세 겹이 각각 V 번 돕니다. 그래서 완화를 V × V × V 번 합니다. 걸리는 시간은 O(V³) 입니다. 노드가 두 배가 되면 여덟 배가 걸립니다. 노드가 1000 개면 완화를 십억 번쯤 합니다.

이 시간은 간선 수와 상관이 없습니다. 간선이 거의 없는 그래프도 빽빽한 그래프와 똑같이 V³ 번 완화합니다. 비어 있는 칸도 빠짐없이 훑기 때문입니다.

메모리는 거리 표 한 장, 곧 V × V 칸입니다. O(V²) 로 적습니다. 노드가 1만 개면 1억 칸입니다.

같은 답을 다익스트라 알고리즘을 노드마다 한 번씩 돌려서 얻을 수도 있습니다. 둘을 견주면 이렇습니다. log V 는 V 를 1 이 될 때까지 반으로 나눈 횟수입니다. 노드가 백만 개여도 스물 남짓입니다.

간선이 V² 에 가까우면 다익스트라 쪽은 V³ log V 가 되어 플로이드보다 더 걸립니다. 도로망처럼 한 노드에 이웃이 몇 개뿐이면 E 가 V 의 몇 배라 다익스트라 쪽은 V² log V 쯤입니다. 이때는 다익스트라 쪽이 덜 걸립니다. 음수 가중치가 있으면 다익스트라 알고리즘은 틀린 답을 냅니다.

음수 사이클

이 소절은 앞에서 미뤄 둔 조건 하나를 봅니다. 음수 가중치는 괜찮은데 음수 사이클은 안 되는 까닭과, 그것을 찾아내는 방법입니다.

사이클은 출발한 노드로 돌아오는 길입니다. 음수 사이클은 가중치 합이 음수인 사이클입니다. 음수 사이클이 있으면 그 사이클을 돌 때마다 거리가 줄어듭니다. 끝없이 돌 수 있으니 가장 짧은 거리가 정해지지 않습니다.

플로이드 알고리즘은 음수 사이클을 찾는 데도 쓸 수 있습니다. 절차를 끝낸 뒤 왼쪽 위에서 오른쪽 아래로 이어지는 대각선 칸, 곧 dist[i][i] 를 봅니다. 처음에 0 이던 이 칸이 음수로 내려가 있으면 i 에서 출발해 i 로 돌아오는 합이 음수인 길이 있다는 뜻입니다.

예를 들어 A→B 의 가중치가 1 이고 B→A 의 가중치가 −3 이면 A → B → A 의 합이 −2 입니다. 절차를 돌리면 dist[A][A] 와 dist[B][B] 가 0 보다 작은 값으로 남습니다. 이런 칸이 하나라도 있으면 표의 다른 값들도 답으로 믿을 수 없습니다.

길을 되짚는 법

거리 표만으로는 어느 노드를 거쳐 가야 하는지 모릅니다. 이 소절은 표를 한 장 더 두어 길까지 얻는 방법을 봅니다.

새 표 next 의 i 행 j 열에는 「i 에서 j 로 갈 때 첫걸음으로 가는 노드」를 적습니다. 처음에는 간선이 있는 칸에 도착 노드 j 를 적습니다.

완화로 dist[i][j] 를 고칠 때 next[i][j] 도 next[i][k] 로 고칩니다. k 를 거쳐 가는 길의 첫걸음은 i 에서 k 로 가는 길의 첫걸음과 같기 때문입니다.

길을 얻을 때는 i 에서 시작해 next 를 따라 한 걸음씩 갑니다. 앞의 예에서 B 에서 A 로 가는 길을 따라가면 첫걸음이 C, C 에서 A 로의 첫걸음이 D, D 에서 A 로의 첫걸음이 A 입니다. 길은 B → C → D → A 입니다.

쓸 때와 안 쓸 때

최단 경로를 구하는 절차는 여럿입니다. 아래 표를 위에서부터 차례로 물어, 처음 맞는 줄의 절차를 고릅니다.

플로이드 알고리즘은 코드가 반복문 세 겹뿐이라 틀릴 곳이 적습니다. 노드 수가 작아 V³ 이 부담되지 않는 문제라면 다른 절차보다 옮기기 쉽습니다.

따로 챙길 자료구조도 없습니다. 다익스트라 알고리즘은 다음에 볼 노드를 고르려고 우선순위 큐를 씁니다. 우선순위 큐는 넣은 값 가운데 가장 작은 것을 빨리 꺼내 주는 자료구조입니다. 플로이드 알고리즘에는 거리 표 한 장이면 됩니다.

존슨 알고리즘은 가중치를 음수가 없도록 바꾼 뒤 노드마다 다익스트라 알고리즘을 돌립니다. 그래서 음수 가중치가 있으면서 간선이 적은 그래프에 맞습니다.

마지막 줄은 거리 대신 참과 거짓을 적는 방식입니다. 더하기 대신 「그리고」를, 작은 값 고르기 대신 「또는」을 씁니다. 끝나면 i 에서 j 로 갈 수 있는지를 모든 짝에 대해 담은 표가 나옵니다. 이 표를 이행적 폐쇄라고 합니다. 이 모양의 절차는 워셜 알고리즘이라고 부릅니다.

관련 항목

플로이드 알고리즘이 속하는 상위 분류

알고리즘 · 그래프 알고리즘 · 최단 경로 · 모든 쌍 최단 경로 · 동적 계획법

플로이드 알고리즘이 도는 그래프의 구성 요소

그래프 · 노드 · 정점 · 간선 · 가중치 · 가중 그래프 · 방향 그래프 · 인접 행렬

같은 최단 경로 문제를 푸는 다른 알고리즘

다익스트라 알고리즘 · 벨만-포드 알고리즘 · 존슨 알고리즘 · 너비 우선 탐색 · A 스타 알고리즘

플로이드 알고리즘이 기대는 성질과 동작

완화 · 최적 부분 구조 · 음수 가중치 · 사이클 · 음수 사이클 · 최단 경로 트리

같은 세 겹 반복 모양으로 푸는 계산

워셜 알고리즘 · 이행적 폐쇄 · 도달 가능성 · 행렬 곱

걸리는 시간을 적는 표기

빅오 표기법 · 시간 복잡도 · 공간 복잡도 · 로그 함수

코드로 옮길 때 다루는 값과 오류

무한대 · 정수 오버플로 · 2차원 배열 · 부동소수점