Transitive Closure and All-Pairs Shortest Paths — 도달 가능성과 모든 쌍 최단 경로, 그리고 Floyd-Warshall

방향 그래프에서 “$u$에서 $v$로 갈 수 있는가”라는 질문은 단일 경로 탐색으로 매번 풀 수도 있다. 하지만 모든 정점 쌍에 대해 이 질문을 반복적으로 던져야 한다면, 도달 가능성 정보를 미리 한 번에 계산해 두는 편이 낫다. 이 발상이 추이적 폐쇄(Transitive Closure)이고, 여기에 간선 가중치를 더하면 모든 쌍 최단 경로(All-Pairs Shortest Paths) 문제가 된다. 두 문제는 놀랍도록 비슷한 구조를 가지며, 같은 동적 계획법 틀로 풀린다.

추이적 폐쇄

방향 그래프(digraph) $G$가 주어졌을 때, $G$의 추이적 폐쇄는 다음 조건을 만족하는 방향 그래프 $G^*$이다.

• $G^*$는 $G$와 같은 정점 집합을 가진다.
• $G$에 $u$에서 $v$로 가는 방향 경로(directed path)가 존재하면($u \neq v$), $G^*$에는 $u$에서 $v$로 가는 방향 간선(directed edge)이 존재한다.

즉 원래 그래프에서 여러 간선을 거쳐야 닿을 수 있던 정점을, $G^$에서는 간선 하나로 바로 연결해 버린다. $A \to C$와 $C \to D$가 있으면 $A \to D$ 간선을 새로 만드는 식이다. 결과적으로 $G^$는 그래프의 도달 가능성(reachability) 정보를 그대로 담는다. $G^*$에 $u \to v$ 간선이 있다는 것은 곧 $G$에서 $u$가 $v$에 도달할 수 있다는 뜻이다.

예를 들어 정점 ${A, B, C, D, E}$에 대해 $G$가 다음 간선을 가진다고 하자.

B → D    D → E    A → C    C → D

여기서 $A$는 $C \to D \to E$를 거쳐 $E$까지 닿는다. $B$는 $D \to E$로 $E$에 닿는다. 이런 모든 도달 관계를 직접 간선으로 추가한 것이 $G^*$다. $A \to D$, $A \to E$, $B \to E$, $C \to E$ 같은 간선이 새로 생긴다.

단순한 방법: 정점마다 DFS

추이적 폐쇄를 구하는 가장 직관적인 방법은 각 정점에서 한 번씩 DFS(또는 BFS)를 돌리는 것이다. 정점 $u$에서 DFS를 시작해 도달하는 모든 정점 $v$에 대해 $u \to v$ 간선을 추가하면 된다.

정점 하나당 DFS는 $O(n + m)$이고, 이를 $n$개의 정점에 대해 반복하므로 전체 복잡도는 다음과 같다.

여기서 $n$은 정점 수, $m$은 간선 수다. 밀집 그래프에서 $m = O(n^2)$이면 $O(n^3)$이 된다.

Floyd-Warshall 알고리즘

DFS를 정점마다 반복하는 대신, 동적 계획법(Dynamic Programming)으로 추이적 폐쇄를 구하는 것이 Floyd-Warshall 알고리즘이다. 핵심 아이디어 두 가지로 정리된다.

• 아이디어 1: 정점에 $1, 2, \dots, n$으로 번호를 매긴다.
• 아이디어 2: 중간 정점(intermediate vertex)으로 $1, 2, \dots, k$번 정점만 사용하는 경로를 단계적으로 고려한다.

여기서 “중간 정점”이란 경로의 시작점과 끝점을 제외한, 경로가 거쳐 가는 정점을 말한다. 핵심 점화 관계는 이렇다. 정점 $i$에서 $j$로 가는 경로가 중간 정점으로 $1, \dots, k$만 사용한다고 하자. 이 경로는 두 경우 중 하나다.

1. $k$번 정점을 거치지 않는다 → 중간 정점으로 $1, \dots, k-1$만 쓰는 $i \to j$ 경로가 이미 존재한다.
2. $k$번 정점을 거친다 → $i \to k$ 경로와 $k \to j$ 경로가 각각 중간 정점으로 $1, \dots, k-1$만 써서 존재한다.

따라서 “$i \to k$가 가능하고 $k \to j$가 가능하면, $i \to j$ 간선을 (없을 경우) 추가한다”는 갱신을 $k$를 $1$부터 $n$까지 늘려가며 반복하면 된다.

일련의 그래프 $G_0, \dots, G_n$

알고리즘은 정점을 $v_1, \dots, v_n$으로 번호 매기고, 그래프 수열 $G_0, G_1, \dots, G_n$을 계산한다.

• $G_0 = G$ (원래 그래프, 중간 정점을 하나도 안 쓰는 직접 간선만)
• $G_k$는 $G$에 $v_i$에서 $v_j$로 가는 경로가 중간 정점을 ${v_1, \dots, v_k}$ 안에서만 거쳐 존재하면 방향 간선 $(v_i, v_j)$를 가진다.
• 최종적으로 $G_n = G^*$ (모든 정점을 중간 정점으로 허용 = 모든 도달 관계)

단계 $k$에서 $G_k$는 직전 단계 $G_{k-1}$로부터 계산된다.

Algorithm FloydWarshall(G)
    Input  digraph G
    Output transitive closure G* of G

    i ← 1
    for all v ∈ G.vertices()
        denote v as v_i
        i ← i + 1
    G_0 ← G
    for k ← 1 to n do
        G_k ← G_{k-1}
        for i ← 1 to n (i ≠ k) do
            for j ← 1 to n (j ≠ i, k) do
                if G_{k-1}.areAdjacent(v_i, v_k) ∧ G_{k-1}.areAdjacent(v_k, v_j)
                    if ¬G_k.areAdjacent(v_i, v_j)
                        G_k.insertDirectedEdge(v_i, v_j, k)
    return G_n

복잡도

세 겹의 반복문이 각각 $n$번 도므로 시간 복잡도는 다음과 같다.

단, 이 분석은 areAdjacent 연산이 $O(1)$이라는 가정에 의존한다. 두 정점의 인접 여부를 상수 시간에 확인하려면 그래프를 인접 행렬(adjacency matrix)로 표현해야 한다. 인접 리스트로 표현하면 인접 확인에 추가 비용이 들어 이 복잡도가 깨진다. 공간 복잡도는 인접 행렬 크기인 $O(n^2)$이다.

Floyd-Warshall 동작 예시

정점 7개짜리 항공 노선 그래프로 알고리즘이 어떻게 행렬을 채워 나가는지 본다. 정점 번호는 다음과 같이 매긴다.

초기 인접 행렬 $G_0$는 직접 연결된 간선만 $1$로 표시한다. 행이 출발, 열이 도착이다.

각 반복 $k$는 “$k$번 정점을 중간 경유지로 허용했을 때 새로 생기는 도달 관계”를 행렬에 채운다. 자기 자신으로의 경로(self-loop)는 고려하지 않으므로 대각선은 그대로 둔다.

• Iteration 1 ($k=1$, LAX 경유 허용): $i \to 1$이고 $1 \to j$인 쌍을 찾는다. $1 \to 4$(LAX→ORD)가 있으므로, $5 \to 1$(MIA→LAX)을 가진 정점 5는 $5 \to 4$(MIA→ORD)에 새로 도달한다.
• Iteration 2 ($k=2$, SFO 경유): SFO는 나가는 간선이 없다($v_2$ 행이 전부 $0$). 따라서 $2 \to j$가 하나도 없어 새 간선이 추가되지 않는다.
• Iteration 3 ($k=3$, DFW 경유): DFW는 LAX, SFO, ORD로 나간다. DFW에 도달하던 정점들(ORD, MIA, JFK 등)이 DFW를 거쳐 LAX·SFO·ORD로 무더기로 연결된다. 이 단계에서 간선이 가장 많이 추가된다.
• Iteration 4 ($k=4$, ORD 경유): ORD는 DFW로 나가므로, ORD에 도달하던 정점들이 DFW에 연결된다. $1 \to 2$, $1 \to 3$ 등이 채워진다.
• Iteration 5 ($k=5$, MIA 경유): MIA를 거쳐 BOS가 ORD·SFO·DFW·LAX로 연결된다.
• Iteration 6 ($k=6$, JFK 경유): JFK를 경유하는 도달 관계가 마저 채워진다.

$k=7$(BOS)까지 마치면 $G_7 = G^*$가 완성된다. 최종 행렬은 각 정점에서 도달 가능한 모든 정점이 $1$로 채워진 형태가 된다.

SFO($v_2$) 행이 끝까지 전부 $0$인 점에 주목하자. SFO는 나가는 간선이 없으니 어디에도 도달하지 못하고, 추이적 폐쇄에서도 마찬가지다.

모든 쌍 최단 경로

추이적 폐쇄가 “도달할 수 있는가(yes/no)”를 물었다면, 모든 쌍 최단 경로(All-Pairs Shortest Paths)는 한 걸음 더 나아가 “최소 비용이 얼마인가”를 묻는다. 가중 방향 그래프(weighted directed graph) $G$에서 모든 정점 쌍 사이의 최단 거리를 구하는 문제다.

방법 1: Dijkstra를 $n$번

음수 간선이 없다면, 각 정점을 출발점으로 삼아 Dijkstra 알고리즘을 $n$번 돌리면 된다. Dijkstra 한 번이 우선순위 큐(힙) 구현 기준 $O(m \log n)$이므로 전체는 다음과 같다.

희소 그래프(sparse graph)에서는 이 방법이 유리하다.

방법 2: 동적 계획법으로 $O(n^3)$

Floyd-Warshall과 같은 동적 계획법 틀을 쓰면 $O(n^3)$에 풀 수 있다. 추이적 폐쇄에서 “도달 가능 여부”를 갱신하던 자리에, 여기서는 “최단 거리”를 갱신한다.

$D_k[i, j]$를 “중간 정점으로 $1, \dots, k$번만 사용했을 때 $i$에서 $j$까지의 최단 거리”로 정의한다. 점화식은 다음과 같다.

직관은 추이적 폐쇄와 똑같다. $i \to j$ 최단 경로가 $k$번 정점을 거치지 않으면 첫 번째 항이고, 거치면 $i \to k$ 최단 거리와 $k \to j$ 최단 거리의 합인 두 번째 항이다. 둘 중 작은 값을 취한다. 추이적 폐쇄의 논리 OR(∧로 연결해 간선을 추가하던 것)가 여기서는 덧셈과 min으로 바뀐 셈이다.

Algorithm AllPair(G)   {정점이 1, …, n으로 번호 매겨져 있다고 가정}
    for all vertex pairs (i, j)
        if i = j
            D_0[i, i] ← 0
        else if (i, j) is an edge in G
            D_0[i, j] ← weight of edge (i, j)
        else
            D_0[i, j] ← +∞
    for k ← 1 to n do
        for i ← 1 to n do
            for j ← 1 to n do
                D_k[i, j] ← min{ D_{k-1}[i, j], D_{k-1}[i, k] + D_{k-1}[k, j] }
    return D_n

초기화 $D_0$가 세 갈래라는 점이 핵심이다. 자기 자신까지의 거리는 $0$, 직접 간선이 있으면 그 가중치, 둘 다 아니면 $+\infty$(도달 불가)로 둔다. 이후 세 겹 반복문이 $k$를 늘려가며 거리를 줄여 나간다.

구현 최적화로, 갱신 시 $D_{k-1}[i, k]$가 $0$이거나 $+\infty$이면 그 $i$에 대해서는 어떤 $j$로도 거리가 줄어들 여지가 없으므로 안쪽 루프를 건너뛸 수 있다.

복잡도

세 겹 반복문이므로 시간 복잡도는 $O(n^3)$, 거리 행렬을 저장하므로 공간 복잡도는 $O(n^2)$이다. 밀집 그래프에서는 Dijkstra를 $n$번 돌리는 $O(nm \log n) = O(n^3 \log n)$보다 빠르고, 무엇보다 구현이 단순하다.

두 문제의 공통 구조

추이적 폐쇄와 모든 쌍 최단 경로는 같은 동적 계획법 골격을 공유한다. 차이는 “무엇을 갱신하는가”뿐이다.

이렇게 “중간 정점을 $1$부터 $n$까지 한 단계씩 허용하며 정보를 누적한다”는 발상이 두 문제를 관통한다. 같은 틀에 어떤 반환값(boolean이냐, 거리냐)과 어떤 결합 연산(AND/OR이냐, +/min이냐)을 끼우느냐에 따라 서로 다른 문제가 풀리는 것이다.