최단 경로 문제 & 벨만-포드 알고리즘 (Shortest Path Problem & Bellman-Ford Algorithm)

Photo by Denys Nevozhai on Unsplash

자동차를 타고 서울에서 부산까지 여행을 떠난다고 생각해 봅시다. 일분일초라도 여행을 더 즐기기 위해서는 빨리 목적지에 도달하는 것이 좋겠죠. 그러려면 어떤 경로를 따라 자동차를 운전해야 할까요? 한 가지 방법으로는 서울에서 부산까지 가는 모든 경로를 따져 본 다음, 가장 빨리 도달할 수 있는 경로를 선택하는 것입니다. 하지만 이 방법은 한눈에 봐도 멍청하다는 것을 알 수 있습니다. 서울에서 부산까지 가는 경로는 엄청나게 많기 때문입니다.

 

여기서 곰곰이 생각해 보면, 우리는 모든 경로를 다 탐색할 필요가 없어 보입니다. 예를 들어, 서울에서 부산까지 가는데 굳이 둘러 둘러 광주를 경유할 필요는 없겠죠. 반대로 서울과 부산의 가운데 정도에 위치한 대전은 지나는 것이 좋을 것입니다. 과연 어떻게 하면 효율적으로 경유할 장소를 판단할 수 있을까요?

 

실생활에서 쉽게 접할 수 있는 위 예시를 컴퓨터과학에서는 최단 경로 문제(shortest path problem)로 정형화 하였습니다. 이번 포스트에서는 이 문제가 무엇이고, 어떻게 하면 다항 시간에 이 문제를 해결할 수 있는지 함께 알아 보도록 하겠습니다.

문제 정의

최단 경로 문제는 다음과 같이 정의됩니다. 문제의 입력으로는 어떤 방향이 있는 그래프(directed graph) $G=(V,E)$와 간선의 비용 $c:E\to \mathbb{Q}$, 그리고 출발지 $s\in V$가 주어집니다. 여기서 "비용"이라고 이름을 붙인 이유는 $c$가 음수를 가질 수도 있기 때문입니다. 거리나 시간이 음수인 것은 말이 안 되지만 음수의 비용은 이익이라 생각할 수도 있으니 말이죠.

그림 1. 최단 경로 문제의 입력 예시.

입력으로 주어지는 그래프 $G$에는 한 가지 제약 조건이 있습니다. 바로 $G$ 위의 어떤 순환(cycle)에 대해서든, 이 순환 위의 간선의 비용을 모두 합하면 항상 0보다는 크거나 같아야 한다는 것입니다. 간선 비용의 합이 음수인 순환을 음의 순환(negative cycle)이라고 부르도록 하겠습니다. 음의 순환이 존재하지 않는다고 가정하는 이유는 마지막 절에서 논증하였습니다.

그림 2. 불가능한 입력 예시. 이는 그림 1의 그래프에서 $c(v,u)$의 값을 $-2$에서 $-5$로 바꾼 것이다. $⟨u,x,y,w,v⟩$가 $-1$의 비용을 갖는 음의 순환이다.

이제 문제의 목표를 알아보겠습니다. 우리는 모든 정점 $v\in V$에 대해, 출발지 $s$에서 $v$까지의 경로(path) 중 가장 비용이 적은 것, 즉, 최단 경로(shortest path)를 찾아야합니다. 만약 그러한 경로가 여러 개 있다면 그중 아무것 하나를 찾으면 됩니다.

 

서두에서 소개한 예시에서는 부산이라는 특정한 도착지가 있었습니다. 하지만 문제의 목표에서는 도착지를 따로 두지 않았죠. 그렇지만 어차피 모든 정점에 대한 최단 경로를 구할 수 있다면, 어느 특정 도착지로 가는 최단 경로도 바로 구할 수 있습니다. 따라서 지금 푸는 문제가 더 일반적인 문제라는 사실을 알 수 있습니다.

 

아래에서 사용할 기호를 소개하겠습니다.

• 어떤 경로의 간선의 개수를 경로의 길이라고 말하겠습니다. 반대로 어떤 경로의 간선의 비용을 모두 더한 것을 경로의 비용이라고 부르겠습니다. 순환에 대해서도 동일한 방식으로 부릅니다.
• 어떤 경로 $P$가 주어졌을 때, 이것의 비용은 $c(P)$라고 표현하겠습니다. 순환이 주어졌을 때도 해당 순환의 비용을 비슷한 기호로 표현합니다.
• 임의의 정점 $v\in V$에 대해, $N^{-}(v)$는 $v$로 들어오는 방향으로 인접한 정점들의 집합, 즉 $$N^{-}(v):=\{u\in V\mid ⟨u,v⟩\in E\}$$를 의미합니다.

최단 경로의 성질

최단 경로를 구하는 알고리즘을 알아보기 전에 최단 경로가 가지는 흥미로운 성질들을 먼저 공부해 보겠습니다. 아래 소개할 성질들은 나중에 보여드릴 알고리즘을 분석할 때 요긴하게 사용됩니다.

 

첫 번째 성질은 어떤 정점 $v$에 대해서든 $s$에서 $v$로 향하는 최단 경로 중에는 반드시 단순 경로(simple path)가 있다는 것입니다. 참고로 단순 경로는 순환이 포함되지 않은 경로를 의미합니다.

정리 1. 최단 단순 경로

---

음의 순환이 없는 방향 그래프 $G=(V,E)$와 간선 비용 $c:E\to \mathbb{Q}$가 주어졌다고 하자. 임의의 두 정점 $u,v\in V$에 대해 $u$에서 $v$로 도달 가능(reachable)할 때, $u$에서 $v$까지로 향하는 $G$에서의 최단 경로 중에는 반드시 단순 경로가 존재한다.

[증명] 만약 $u=v$라면 자명한 경로 $⟨u⟩$가 존재하므로 $u\ne v$라고 하겠습니다. 이제 $u$에서 $v$로 가는 임의의 최단 경로 $P$를 하나 잡겠습니다. 만약 $P$에 순환이 없으면 바로 정리가 증명이 되므로, $P$에 순환이 존재한다고 하겠습니다. 그러면 우리는 $P$가 다음과 같은 꼴이 된다는 것을 알 수 있습니다.

$$P=⟨u,\cdots ,w,x,\cdots ,y,z,\cdots ,v⟩\text{ (단, }x=y\text{)}$$

이제 다음과 같은 경로 $P^{\prime }$을 생각해 봅시다.

$$P^{\prime }=⟨u,\cdots ,w,x,z,\cdots ,v⟩$$

이 경로는 $P$에서 순환 $⟨x,\cdots ,y⟩$를 제거한 것입니다.

 

그러면 우리는 쉽게 $P^{\prime }$이 $u$에서 $v$로 향하는 경로 중 하나라는 것을 알 수 있습니다. 더구나 우리는 $G$에 음의 순환이 없다고 하였으므로, 순환 $⟨x,\cdots ,y⟩$의 비용은 분명 0보다 크거나 같습니다. 따라서 $P^{\prime }$의 비용이 $P$보다 비싸지 않을 것입니다. 즉, $P^{\prime }$도 $u$에서 $v$로 가는 최단 경로가 됩니다.

 

아직 증명이 끝나지 않았습니다. $P^{\prime }$에 여전히 순환이 있을 수 있기 때문이죠. 하지만 $P^{\prime }$의 길이는 $P$보다 짧기만 합니다. 따라서 $P^{\prime }$에 대해서 위 작업을 똑같이 진행하면 $u$에서 $v$로 향하면서 길이는 짧기만 한 최단 경로를 구할 수 있습니다. 이를 순환이 없을 때까지 진행하면 됩니다. 길이가 짧아지기만 하므로 "최악"의 상황에도 결국 $⟨u,v⟩$를 얻게 됩니다. 이는 단순히 간선 하나이고, $u\ne v$이므로 순환이 아닙니다. 따라서 위 작업을 계속 하다보면 언젠간 순환이 없는 $u$에서 $v$로 향하는 최단 경로를 얻게 되며, 이로써 증명이 완성됩니다. ■

그림 3. 최단 단순 경로 예시. $⟨s,v,w,x,y,w,x,z⟩$는 $s$에서 $z$로 향하는 순환이 있는 최단 경로이다. 여기서 순환 $⟨w,x,y,w⟩$를 제거하면 $⟨s,v,w,x,z⟩$를 얻을 수 있고, 이는 순환이 없는 최단 경로가 된다.

정리 1을 통해서 우리는 모든 경로에 대해서 생각할 필요 없이, 단순 경로 중에서 최단 경로가 되는 것만 따져 보면 된다는 것을 알 수 있습니다. 다만 여전히 임의의 두 정점 사이의 단순 경로도 매우 많기 때문에 단순 경로를 모두 순회할 수는 없습니다. 따라서 최단 경로를 효율적으로 구하기 위해서는 좀더 특별한 성질을 찾아야 합니다. 다음 정리를 통해 그것이 무엇인지 확인할 수 있습니다.

정리 2. 최단 경로들의 관계

---

임의의 방향 그래프 $G=(V,E)$와 간선 비용 $c:E\to \mathbb{Q}$ 그리고 출발지 $s\in V$가 주어졌다고 하자. 임의의 정점 $v\in V$에 대해, $P=⟨s,\cdots ,u,v⟩$가 $s$에서 $v$로 향하는 최단 경로라고 하자. 그러면 아래가 모두 성립한다.

• $P$에서 마지막 $v$를 제거한 $P^{\prime }$은 $s$에서 $u$까지 향하는 최단 경로이다.
• $Q^{\prime }$을 $s$에서 $u$로 향하는 $P^{\prime }$과 다른 최단 경로라고 할 때, $s$에서 $Q^{\prime }$을 따라 $u$에 도착한 다음 $v$로 가는 경로 $Q$도 $s$에서 $v$까지 가는 최단 경로이다.

[증명] 첫 번째 명제는 귀류법으로 증명합니다. $P^{\prime }$이 $s$에서 $u$로 향하는 최단 경로가 아니라고 하겠습니다. 대신 $P^{″}$이 $s$에서 $u$로 향하는 최단 경로라고 하겠습니다. 그러면 $s$에서 $P^{″}$을 통해 $u$에 도착한 후 $v$로 가는 것도 $s$에서 $v$로 가는 경로 중 하나입니다. 이 경로의 비용은 $$c(P^{″})+c(u,v)<c(P^{\prime })+c(u,v)=c(P)$$이므로 $P$가 $s$에서 $v$로 가는 최단 경로라는 것에 모순이 됩니다.

 

두 번째 명제는 $$c(Q)=c(Q^{\prime })+c(u,v)=c(P^{\prime })+c(u,v)=c(P)$$이므로 쉽게 보일 수 있습니다. ■

 

앞에서 배운 정리들을 토대로 우리는 다음과 같은 사실을 유추할 수 있습니다. 먼저 정리 2를 통해 알 수 있는 것은 $s$에서 어느 정점 $v$까지의 최단 경로를 구할 때, $s$에서 $v$로 향하는 모든 경로를 생각할 필요 없이, $v$로 들어오는 간선 중 최단 경로 상 직전의 정점을 찾는 것으로 충분하다는 것입니다. 각 $v\in V\setminus \{s\}$마다 해당 이전 정점을 $\pi (v)$라고 하겠습니다.

 

정리 1에서 음의 순환이 없는 그래프 위에서는 단순한 최단 경로가 존재한다고 했습니다. 그러므로 그래프 위에 $⟨\pi (v),v⟩$를 모두 표시해 보면 순환이 생기지 않습니다. 엄밀히 말해, $F:=\{⟨\pi (v),v⟩\in E\mid v\in V\setminus \{s\}\}$라고 했을 때, $(V,F)$는 $s$를 루트(root)로 하는 방향이 있는 트리(directed tree, arborescence)를 이루게 됩니다.

 

흥미로운 점은, 간단한 수학적 귀납법을 사용하면, 임의의 정점 $v$에 대해, 이 트리 위에서 $s$에서 $v$까지 가는 경로가 곧 원래 그래프에서 최단 경로가 된다는 사실입니다. 이 트리를 우리는 종종 최단 경로 트리(shortest path tree)라고도 부르며 이것이 바로 최단 경로들이 갖는 흥미로운 구조적 특질입니다. 따라서 최단 경로 트리를 효율적으로 찾는 것이 곧 최단 경로 문제를 해결하는 중요한 열쇠가 됩니다.

그림 4. 최단 경로 트리의 예시.

점화식 세우기

이전 절에서 최단 경로 문제를 해결하기 위해서는 최단 경로 트리를 만드는 것이 중요하다고 하였습니다. 그러기 위해서는 각 정점 $v$마다 최단 경로 상 직전 정점 $\pi (v)$가 무엇인지를 알아내야 합니다. 이번 절에서는 이를 구하기 위한 적절한 점화식을 함께 공부해 보겠습니다.

 

첫 번째로 자연스럽게 생각할 수 있는 점화식은 다음과 같습니다. 각 정점 $v\in V$에 대해, $\mathsf{OPT}(v)$를 $s$에서 $v$까지의 최단 경로의 비용이라고 하겠습니다. 이제, 각 정점 $v\in V$에 대해, $$\begin{array}{}\text{(1)}& \mathsf{OPT}(v)=\{\begin{array}{ll}0,& \text{ if }v=s,\\ \underset{u\in N^{-}(v)}{min}\{\mathsf{OPT}(u)+c(u,v)\},& \text{ otherwise,}\end{array}\end{array}$$라는 점화식을 세우겠습니다. 정리 2를 통해서 우리는 이 점화식이 항상 성립한다는 것을 어렵지 않게 증명할 수 있습니다.

 

점화식을 세웠으니 이를 따라 알고리즘을 짜면 되겠죠. 그런데 그게 과연 가능할까요? 안타깝지만 쉽지 않습니다. 왜냐하면 위 점화식은 입력으로 주어지는 그래프에 순환이 있으면 자기 참조(self-reference)에 빠지기 때문입니다.

그림 5. 점화식 1에서 자기 참조의 예시

예를 들어, 그림 5에서 $\mathsf{OPT}(w)$를 구하기 위해서는 $\mathsf{OPT}(v)$와 $\mathsf{OPT}(y)$를 정확히 알고 있어야 합니다. 여기서 $\mathsf{OPT}(y)$를 구하려면 $\mathsf{OPT}(x)$와 $\mathsf{OPT}(z)$의 값을 갖고 있어야 하죠. 근데 이 중에서 $\mathsf{OPT}(x)$는 $\mathsf{OPT}(u)$, $\mathsf{OPT}(v)$, $\mathsf{OPT}(w)$에 의존합니다. 따라서 $\mathsf{OPT}(w)$를 구하기 위해서 결국 $\mathsf{OPT}(w)$를 알고 있어야 하는 상황에 빠지게 됩니다.

 

이 상황을 컴퓨터과학적으로 해결하는 것은 매우 어렵습니다. 비록 정리 1을 통해 최단 경로에 순환이 없다는 사실을 알고 있어도, 직전 정점에 대한 정보가 전혀 없이는 어떤 방법으로 점화식을 풀어갈 수 있는지 알기 어렵습니다.^[ㄱ] 과연 어떻게 이를 해결할 수 있을까요?

 

점화식을 잘 들여다 보면 힌트를 얻을 수 있습니다. $\mathsf{OPT}(v)=\mathsf{OPT}(u)+c(u,v)$가 의미하는 것이 무엇인가요? 이는 $s$에서 $v$로 가는 최단 경로는 $s$에서 $u$로 가는 최단 경로에서 간선 $⟨u,v⟩$를 추가한다는 의미입니다. 이 작업에서 우리는 경로의 길이가 증가한다는 것을 확인할 수 있습니다.

 

따라서 다음과 같이 경로의 길이가 추가된 점화식을 생각해 볼 수 있겠습니다. 각 정점 $v\in V$와 음이 아닌 정수 $k\ge 0$에 대해 $\mathsf{OPT}(v,k)$를 $s$에서 $v$까지 길이가 $k$를 넘지 않는 경로의 비용 중 가장 적은 값으로 정의하겠습니다. 그러면 아래 정리가 성립합니다.

정리 3. 알고리즘으로 해결 가능한 점화식

---

다음 점화식이 성립한다.

$$\begin{array}{}\text{(2)}& \mathsf{OPT}(v,k)=\{\begin{array}{ll}0,& \text{ if }v=s,k=0,\\ \mathrm{\infty },& \text{ if }v\ne s,k=0,\\ min\{\begin{array}{c}\mathsf{OPT}(v,k-1)\\ \underset{u\in N^{-}(v)}{min}\{\mathsf{OPT}(u)+c(u,v)\}\end{array},& \text{ if }k>0.\end{array}\end{array}$$ 

[증명] 만약 $v=s$이면 길이가 0인 자명한 경로 $⟨s⟩$가 존재하므로 $\mathsf{OPT}(s,0)=0$임을 알 수 있습니다. 반대로 $v\ne s$이고 $k=0$이면, $v$는 $s$에서 간선을 하나도 쓰지 않고 도달할 방법이 없으므로 $\mathsf{OPT}(v,0)=\mathrm{\infty }$가 됩니다.

 

마지막으로 가장 복잡한 $k>0$ 경우를 살펴보겠습니다. 만약 $s$에서 $k$ 이하의 간선으로 $v$에 도달할 수 없다면 $v$는 물론 $N^{-}(v)$의 정점 $u$도 $k-1$ 이하의 간선으로 $s$에서 도달할 수 없으므로 $\mathsf{OPT}(v,k)$ $=\mathsf{OPT}(v,k-1)$ $=\mathsf{OPT}(u,k-1)$ $=\mathrm{\infty }$가 되어 성립합니다. 반대로 $s$에서 길이 $k$ 이하로 $v$에 도달 가능하면, 해당 경로 중 가장 적은 비용을 갖는 경로는 길이가 $k-1$ 이하거나 $N^{-}(v)$의 한 정점 $u$까지 길이 $k-1$ 이하로 도달한 다음 $⟨u,v⟩$를 따라가는 것이므로 점화식이 성립합니다. ■

 

정리 3의 점화식을 보면 자기 참조가 일어날 수 없는 구조라는 것을 쉽게 알 수 있습니다. 왜냐하면 $k>0$일 때, $\mathsf{OPT}(\cdot ,k)$가 $\mathsf{OPT}(\cdot ,k-1)$에만 의존하기 때문입니다. 따라서 이는 알고리즘으로 차근히 계산할 수 있는 구조입니다.^[ㄴ] 문제는 길이 $k$가 무한정 길어질 수 있다는 점인데, 우리는 정리 1에서 최단 경로 중에는 단순한 최단 경로가 항상 존재한다는 것을 알고 있습니다. 따라서 다음 정리를 쉽게 유추할 수 있습니다.

정리 4. 점화식 1과 점화식 2의 관계

---

임의의 $v\in V$에 대해, $\mathsf{OPT}(v)=\mathsf{OPT}(v,|V|-1)$이다.

벨만-포드 알고리즘 (Bellman-Ford algorithm)

앞에서 우리는 점화식 2가 자기 참조도 없으면서 $k=|V|-1$일 때의 값이 최단 경로의 비용과 동일하다는 것을 보였습니다. 이를 근거로 다음과 같은 알고리즘을 만들어 봅시다.

알고리즘 1. Bellman-Ford algorithm

---

입력: 음의 순환이 없는 방향 그래프 $G=(V,E)$, 간선 비용 $c:E\to \mathbb{Q}$, 출발점 $s$

출력: 최단 경로 트리

 

1. 2차원 배열 $d$에 대해, $d[v][k]\leftarrow \mathrm{\infty }$; 단, $d[s][0]\leftarrow 0$
2. 1차원 배열 $\pi$에 대해, $\pi [v]\leftarrow \mathsf{NULL}$
3. $k=1,\cdots ,|V|-1$에 대해:
   1. 각 정점 $v\in V$에 대해:
      1. 각 정점 $u\in N^{-}(v)$에 대해, 만약 $d[v][k]>d[u][k-1]+c(u,v)$이면,
         $d[v][k]\leftarrow d[u][k-1]+c(u,v)$
         $\pi [v]\leftarrow u$
4. $\pi$를 갖고 최단 경로 트리를 만든다.

이 알고리즘이 올바르게 동작한다는 것은 앞에서 모두 보였습니다. 따라서 남은 것은 이 알고리즘의 수행 시간을 계산하는 것입니다.

정리 5. 알고리즘 1의 수행 시간

---

알고리즘 1은 $O(|V||E|)$ 시간에 동작한다.

[증명] 단계 1은 $O(|V{|}^2)$, 단계 2와 4는 $O(|V|)$에 수행이 가능합니다. 남은 것은 단계 3의 수행 시간을 분석하는 것입니다. 각 정점 $v\in V$에 대해, 단계 3-i-a는 $O(|N^{-}(v)|)$에 동작합니다. 따라서, 단계 3-i은 $O(\sum _{v\in V}|N^{-}(v)|)$ 시간이 필요하다는 것을 알 수 있습니다. 우리는 방향 간선들을 같은 도착 정점을 갖는 간선들로 분할(partition)할 수 있고, 각 $v\in V$에 대해, $v$를 도착 정점으로 하는 간선들의 개수는 정확히 $|N^{-}(v)|$와 같습니다. 따라서 $$\sum _{v\in V}|N^{-}(v)|=|E|$$임을 알 수 있습니다. 단계 3에서 단계 3-i은 총 $|V|$번 수행하므로 단계 3의 수행 시간은 $O(|V||E|)$가 됩니다. ■

 

이 알고리즘이 바로 벨만-포드 알고리즘(Bellman-Ford algorithm)입니다.

더 효율적인 구현

제 블로그에서 알고리즘의 공간 복잡도를 다룬 적은 잘 없었던 것 같습니다. 특별히 공간에 제약이 있는 경우가 아니라면 보통은 수행 시간에 관심이 많기 때문이죠. 또한, 이론적인 이득이 없는 이상에야 알고리즘을 어떻게 구현하는 것이 좋을지에 대해서도 비중 있게 다룬 적이 없었습니다. 하지만, 벨만-포드 알고리즘에서 만큼은 이 내용도 중요해 보여 짚고 넘어가고자 합니다.

 

알고리즘 1이 사용하는 공간은 얼마나 될까요? $d$가 점근적으로 지배적인 크기를 가질 것이므로 $O(|V{|}^2)$이 필요합니다. 하지만 사실은 이만큼 필요 없습니다. 단계 3-i-a에서 볼 수 있듯이, $d[v][k]$를 결정할 때 필요한 값은 결국 $d[u][k-1]$이므로, $i=0,\cdots ,k-2$에 대해서 $d[u][i]$는 필요하지 않습니다. 따라서 $d[v][k]$의 값을 대신 $d[v][k\mathrm{mod}2]$에 저장한다면 사용하는 공간을 $O(|V|)$로 줄일 수 있습니다. 다만 여전히 $d$는 2차원 배열이기는 하죠.

 

놀랍게도 이보다 더 효율적으로 구현하는 방법이 있습니다.

알고리즘 2. Bellman-Ford algorithm (better implementation)

---

입력: 음의 순환이 없는 방향 그래프 $G=(V,E)$, 간선 비용 $c:E\to \mathbb{Q}$, 출발점 $s$

출력: 최단 경로 트리

 

1. 1차원 배열 $f$에 대해, $f[s]\leftarrow 0$, $f[v]\leftarrow \mathrm{\infty }$ ($v\ne s$)
2. 1차원 배열 $\pi$에 대해, $\pi [v]\leftarrow \mathsf{NULL}$
3. $k=1,\cdots ,|V|-1$에 대해:
   1. 각 간선 $⟨u,v⟩\in E$에 대해, 만약 $f[v]>f[u]+c(u,v)$이면,
      $f[v]\leftarrow f[u]+c(u,v)$
      $\pi [v]\leftarrow u$
4. $\pi$를 갖고 최단 경로 트리를 만든다.

이전 2차원 배열 $d$의 역할을 1차원 배열 $f$로 대신하고, 대신 경로의 길이 $k$에 대한 정보를 없앴습니다. 마치 점화식 1과 비슷한 형태를 보입니다. 앞에서 점화식 1은 풀기 어렵다고 했는데 어째서 알고리즘 2는 올바르게 동작한다는 것일까요? 그 이유는 바로 $|V|-1$번 반복하기 때문입니다. 아래 정리를 통해 이를 엄밀히 밝히도록 하겠습니다.

정리 6. 알고리즘 2의 정당성(correctness)

---

알고리즘 1과 알고리즘 2를 동시에 돌린다고 가정하자. 임의의 $k=0,\cdots ,|V|-1$에 대해, 알고리즘 2가 단계 3을 $k$번 수행한 후의 $f$를 $f_k$라고 하자. 그러면 임의의 정점 $v\in V$에 대해, $$f_k[v]\le d[v][k]$$가 성립한다.

[증명] 수학적 귀납법으로 보이겠습니다. $k=0$일 때는 자명합니다. 이제 $k>0$에 대해서 $f_{k-1}[v]\le d[v][k-1]$이 성립한다고 하겠습니다. 만약 $d[v][k-1]=d[v][k]$인 경우, $$f_k[v]\le f_{k-1}[v]\le d[v][k-1]=d[v][k]$$가 되어 성립합니다. 여기서 첫 번째 부등식은 알고리즘 2의 단계 3이 수행되는 동안에 $f$의 값은 감소하기만 하므로 만족하며, 두 번째 부등식은 귀납 가정(induction hypothesis)에서 왔습니다.

 

이제 $d[v][k-1]<d[v][k]$라고 가정하겠습니다. 알고리즘 1에서 이 상황이 발생하려면 $d[v][k]=d[u][k-1]+c(u,v)$를 만족하는 $u\in N^{-}(v)$가 하나 반드시 존재합니다. 알고리즘 2에서도 분명 $⟨u,v⟩$에 대해 고려를 하므로 다음과 같은 부등식을 이끌어낼 수 있습니다. $$f_k[v]\le f_{k-1}[u]+c(u,v)\le d[u][k-1]+c(u,v)=d[v][k]$$ 여기서 첫 번째 부등식이 성립하는 이유는 알고리즘 2가 단계 3에서 $⟨u,v⟩$을 고려할 때의 $f[u]$ 값이 $f_{k-1}[u]$보다 크지 않기 때문입니다. (둘이 같지 않을 수도 있습니다.) 두 번째 부등식은 똑같이 귀납 가정에서 유도할 수 있습니다. ■

 

정리 6을 통해 알고리즘 2가 최종적으로 유지하는 $f$에 대해 $$f[v]\le d[v][|V|-1]=\mathsf{OPT}(v,|V|-1)=\mathsf{OPT}(v)$$를 이끌어낼 수 있습니다. 알고리즘 2의 $\pi$를 역산하면 $s$에서 $v$까지 향하는 비용이 $f[v]$인 경로가 됩니다. 이로써 알고리즘 2가 올바르다는 것을 확인할 수 있습니다.

음의 순환이 있는 경우

위 알고리즘을 수행하기 위해서는 입력된 방향 그래프에 음의 순환이 없어야 한다는 조건이 있었습니다. 해당 조건은 왜 필요한 것일까요? 이는 정리 1의 증명을 잘 들여다 보면 답을 알 수 있습니다. 어떤 최단 경로에서 순환을 제거해도 무방했던 이유는 해당 순환의 비용이 음수가 아니었기 때문이었습니다. 그렇다면 음의 순환이 있으면 어떻게 될까요? 그 순환을 계속 반복하면 계속 비용이 적어지기만 할 것입니다. 따라서 비용이 $-\mathrm{\infty }$로 발산하게 되겠죠. 다음 정리는 이 내용을 엄밀히 밝혀 적은 것입니다.

정리 7. 음의 순환이 있는 경우

---

어떤 방향 그래프 $G=(V,E)$와 간선 비용 $c:E\to \mathbb{Q}$에 음의 순환이 있다고 하자. 만약 출발지 $s$에서 이 순환의 어느 한 정점에 도달이 가능하다면, 이 순환의 어느 한 정점에서 도달 가능한 모든 정점들의 최단 경로의 비용은 모두 $-\mathrm{\infty }$이다.

 

음의 순환이 존재하면 알고리즘은 고사하고 문제 자체가 망가져 버린다는 것을 확인하였습니다. 그렇다면 음의 순환에 대처할 수 있는 방법은 없는 것일까요? 다행히도 입력 그래프에 음의 순환이 존재하는지 여부를 판단할 수 있습니다. 바로 알고리즘의 단계 3을 한 번 더 수행하는 것이죠. 만약 음의 순환이 있다면 알고리즘은 더 적은 비용의 경로가 있다고 판단할 것이며, 이는 정리 1에 위배가 되므로 음의 순환이 있다고 판단할 수 있습니다.

알고리즘 3. Bellman-Ford algorithm with negative cycle detection

---

입력:방향 그래프 $G=(V,E)$, 간선 비용 $c:E\to \mathbb{Q}$, 출발점 $s$

출력: 최단 경로 트리 또는 음의 순환 존재 여부

 

1. 1차원 배열 $f$에 대해, $f[s]\leftarrow 0$, $f[v]\leftarrow \mathrm{\infty }$ ($v\ne s$)
2. 1차원 배열 $\pi$에 대해, $\pi [v]\leftarrow \mathsf{NULL}$
3. $k=1,\cdots ,|V|-1$에 대해:
   1. 각 간선 $⟨u,v⟩\in E$에 대해, 만약 $f[v]>f[u]+c(u,v)$이면,
      $f[v]\leftarrow f[u]+c(u,v)$
      $\pi [v]\leftarrow u$
4. 어떤 간선 $⟨u,v⟩\in E$에 대해, 만약 $f[v]>f[u]+c(u,v)$이면, 음의 순환이 존재한다.
5. $\pi$를 갖고 최단 경로 트리를 만든다.

마치며

오랜만에 글을 적었습니다. 그동안 저는 논문 작업을 하느라 좀 바빴습니다. 사실 지금 마무리 지을 단계는 아니었는데 예기치 못한 사태가 발생해서 어쩔 수 없이 일찍 마무리하게 되었습니다. 아쉽기는 하지만 유종의 미를 거둘 수 있었으면 합니다. 논문 작업을 할 때는 그걸 하느라 바빠서 블로그 관리를 하지 못했는데, 다 쓴 후에도 영 포스팅을 할 생각이 들지 않았습니다. 이것 저것 다루면 좋겠다는 주제는 머릿속에 있었는데 행동으로 옮기지는 못했습니다. 좀 지쳤나 봅니다.

 

그러다 다시 글을 작성하게된 계기는 좀 부끄러운 일이 생겨서입니다. 언젠가 너무 당당하게 벨만-포드 알고리즘의 수행 시간이 $O(|V{|}^2)$이라고 말한 것이죠. 나름 어언 5년 동안 컴퓨터과학 이론을 전문적으로 공부했고, 알고리즘 과목 조교만 세 번을 했는데 벨만-포드 알고리즘의 수행 시간을 제대로 모른다니요. 자괴감이 들어 제대로 공부한 다음에 글을 적었습니다.

 

이번 일을 계기로 블로그 포스팅도 좀더 해 나갈까 합니다. 읽어주셔서 고맙습니다. :)

참조

[1] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: Introduction to Algorithms, 3rd Edition. MIT Press 2009.

각주

[ㄱ] 단, 입력 그래프에 순환이 없는 경우에는 자기 참조의 모순에 빠지지 않으므로 이 점화식을 사용해 알고리즘을 구현할 수 있습니다. 이는 $O(|V|+|E|)$의 수행 시간을 갖습니다.

 

[ㄴ] 동적 계획법(dynamic programming)에 대한 설명입니다.