고정된 길이의 경로 수 / 고정된 길이의 최단 경로¶

다음 글에서는 같은 아이디어에 기반한 두 문제의 풀이를 설명합니다. 그 아이디어는 문제를 행렬의 구성으로 환원한 뒤, 일반적인 행렬 곱셈 또는 변형된 곱셈으로 해를 계산하는 것입니다.

고정된 길이의 경로 수¶

정점 $n$개로 이루어진 방향 가중치 없는 그래프 $G$와 정수 $k$가 주어집니다. 과제는 다음과 같습니다. 각 정점 쌍 $(i, j)$에 대해 두 정점 사이의 길이가 $k$인 경로의 수를 구해야 합니다. 경로는 단순 경로일 필요가 없습니다. 즉, 하나의 경로에서 정점과 간선을 몇 번이든 방문할 수 있습니다.

그래프는 인접 행렬로 주어진다고 가정합니다. 즉, 크기가 $n \times n$인 행렬 $G[][]$로 주어지며, 각 원소 $G[i][j]$는 정점 $i$가 $j$와 간선으로 연결되어 있으면 $1$이고, 간선으로 연결되어 있지 않으면 $0$입니다. 다음 알고리즘은 다중 간선이 있는 경우에도 동작합니다. 어떤 정점 쌍 $(i, j)$가 $m$개의 간선으로 연결되어 있다면, 인접 행렬에서 $G[i][j] = m$으로 설정하여 이를 기록할 수 있습니다. 또한 이 알고리즘은 그래프에 루프(정점을 자기 자신과 연결하는 간선)가 있는 경우에도 동작합니다.

구성한 인접 행렬이 $k = 1$인 경우의 답이라는 것은 자명합니다. 이 행렬에는 각 정점 쌍 사이의 길이가 $1$인 경로의 수가 담겨 있습니다.

해는 반복적으로 구성하겠습니다. 어떤 $k$에 대한 답을 알고 있다고 가정합시다. 여기서는 $k + 1$에 대한 답을 구성하는 방법을 설명합니다. $k$인 경우의 행렬을 $C_k$로, 구성하려는 행렬을 $C_{k+1}$로 표기합니다. 다음 식으로 $C_{k+1}$의 모든 원소를 계산할 수 있습니다:

$$C_{k+1}[i][j] = \sum_{p = 1}^{n} C_k[i][p] \cdot G[p][j]$$

이 식이 계산하는 것은 다름 아닌 행렬 $C_k$와 $G$의 곱이라는 것을 쉽게 알 수 있습니다:

$$C_{k+1} = C_k \cdot G$$

따라서 문제의 해는 다음과 같이 나타낼 수 있습니다:

$$C_k = \underbrace{G \cdot G \cdots G}_{k \text{ times}} = G^k$$

마지막으로, 이진 거듭제곱을 사용하면 행렬 곱을 효율적으로 높은 거듭제곱까지 올릴 수 있다는 점만 짚어 두면 됩니다. 이렇게 하면 $O(n^3 \log k)$ 복잡도의 풀이를 얻습니다.

고정된 길이의 최단 경로¶

정점 $n$개로 이루어진 방향 가중치 그래프 $G$와 정수 $k$가 주어집니다. 각 정점 쌍 $(i, j)$에 대해 정확히 $k$개의 간선으로 이루어진 $i$와 $j$ 사이의 최단 경로의 길이를 구해야 합니다.

그래프는 인접 행렬로 주어진다고 가정합니다. 즉, 크기가 $n \times n$인 행렬 $G[][]$로 주어지며, 각 원소 $G[i][j]$에는 정점 $i$에서 정점 $j$로 가는 간선의 길이가 담겨 있습니다. 두 정점 사이에 간선이 없으면 행렬의 해당 원소에는 무한대 $\infty$를 할당합니다.

이 형태의 인접 행렬이 $k = 1$에 대한 답이라는 것은 자명합니다. 이 행렬에는 각 정점 쌍 사이의 최단 경로의 길이가 담겨 있으며, 간선 하나로 이루어진 경로가 없으면 $\infty$가 담겨 있습니다.

이번에도 문제의 해를 반복적으로 구성할 수 있습니다. 어떤 $k$에 대한 답을 알고 있다고 가정합시다. $k+1$에 대한 답을 계산하는 방법을 보이겠습니다. $k$에 대한 행렬을 $L_k$로, 구성하려는 행렬을 $L_{k+1}$로 표기합시다. 그러면 다음 식으로 $L_{k+1}$의 각 원소를 계산할 수 있습니다:

$$L_{k+1}[i][j] = \min_{p = 1 \ldots n} \left(L_k[i][p] + G[p][j]\right)$$

이 식을 자세히 살펴보면 행렬 곱셈과의 유사점을 찾을 수 있습니다. 실제로 행렬 $L_k$에 행렬 $G$를 곱하는 것이며, 유일한 차이는 곱셈 연산에서 합 대신 최솟값을 취하고, 내부 연산으로 곱 대신 합을 사용한다는 점입니다.

$$L_{k+1} = L_k \odot G,$$

여기서 연산 $\odot$은 다음과 같이 정의됩니다:

$$A \odot B = C~~\Longleftrightarrow~~C_{i j} = \min_{p = 1 \ldots n}\left(A_{i p} + B_{p j}\right)$$

따라서 이 문제의 해는 변형된 곱셈을 사용하여 다음과 같이 나타낼 수 있습니다:

$$L_k = \underbrace{G \odot \ldots \odot G}_{k~\text{times}} = G^{\odot k}$$

변형된 곱셈은 명백히 결합 법칙을 만족하므로, 이 거듭제곱 역시 이진 거듭제곱을 이용하여 효율적으로 계산할 수 있다는 점만 짚고 넘어가면 됩니다. 따라서 이 풀이 역시 $O(n^3 \log k)$의 복잡도를 가집니다.

길이가 최대 $k$인 경로에 대한 문제의 일반화¶

위의 풀이들은 고정된 $k$에 대한 문제를 해결합니다. 그러나 이 풀이들을 변형하면 경로가 최대 $k$개의 간선을 포함할 수 있는 문제도 해결할 수 있습니다.

이는 입력 그래프를 약간 수정하여 해결할 수 있습니다.

각 정점을 복제합니다: 각 정점 $v$에 대해 정점 $v'$를 하나 더 만들고, 간선 $(v, v')$와 루프 $(v', v')$를 추가합니다. 간선이 최대 $k$개인 $i$와 $j$ 사이의 경로의 수는 간선이 정확히 $k + 1$개인 $i$와 $j'$ 사이의 경로의 수와 같습니다. 길이가 $m \le k$인 모든 경로 $[p_0 = i,~p_1,~\ldots,~p_{m-1},~p_m = j]$를 길이가 $k + 1$인 경로 $[p_0 = i,~p_1,~\ldots,~p_{m-1},~p_m = j, j', \ldots, j']$로 대응시키는 전단사 함수가 존재하기 때문입니다.

같은 기법을 적용하여 간선이 최대 $k$개인 최단 경로도 계산할 수 있습니다. 이번에도 각 정점을 복제하고, 앞서 언급한 두 간선을 가중치 $0$으로 추가합니다.