최단 경로(Shortest Path) 알고리즘

네비게이션의 최단 경로는 어떻게 찾을까? 단순히 가장 짧아 보이는 길을 선택하는 방식으로는 정확한 경로를 찾기 어렵다. 도시에는 수많은 교차로와 도로가 얽혀있고, 모든 경로를 일일이 따져보는 것은 현실적으로 불가능하기 때문이다.

 

이 문제를 우아하게 해결한 사람이 바로 에츠허르 다익스트라(Edsger Dijkstra)다. 하지만 최단 경로 문제는 하나의 알고리즘으로 해결되지 않는다. 그래프의 특성에 따라 다른 접근이 필요하다. 이번 글에서는 다익스트라 알고리즘을 시작으로, 다양한 상황에 맞는 최단 경로 알고리즘들을 살펴보겠다.

 

1. 그래프의 표현: 가중치 인접 행렬(weight adjacent matrix)

최단 경로 문제를 다루기 전에, 먼저 그래프를 어떻게 표현할지 정해야 한다.

 

우리가 다루는 것은 가중치가 있는 유향 그래프(weighted directed graph) G = (V, E)다. 여기서 V는 정점(vertex)들의 집합이고, E는 간선(edge)들의 집합이다. 각 간선에는 거리나 비용을 나타내는 가중치가 붙어있다.

 

이런 그래프를 표현하는 방법 중 하나가 가중치 인접 행렬이다. 행렬의 (i, j) 위치에 정점 i에서 j로 가는 간선의 가중치를 저장한다. 간선이 없으면 무한대(∞)를, 대각선 원소는 0으로 설정한다.

 

예를 들어 정점이 4개인 그래프에서 A→B의 가중치가 5, B→C의 가중치가 3이라면 다음과 같이 표현된다.

	A	B	C	D
A	0	5	∞	∞
B	∞	0	3	∞
C	∞	∞	0	∞
D	∞	∞	∞	0

 

2. 최단 경로 알고리즘의 분류

최단 경로 알고리즘은 크게 두 가지로 나뉜다.

 

단일 시작점 최단 경로(Single-Source Shortest Path)는 하나의 출발점에서 다른 모든 정점까지의 최단 경로를 찾는다. 예를 들어 A에서 B, C, D 각각으로 가는 최단 경로를 구한다. 다익스트라 알고리즘과 벨만-포드 알고리즘이 여기에 속한다.

 

모든 쌍 최단 경로(All-Pairs Shortest Path)는 모든 정점 쌍 사이의 최단 경로를 찾는다. A→B, A→C, B→C, C→D 등 가능한 모든 경로를 구한다. 플로이드-워샬 알고리즘이 대표적이다.

 

3. 다익스트라(Djikstara) 알고리즘

다익스트라 알고리즘은 단일 시작점 최단 경로 문제를 다이나믹 프로그래밍으로 해결한 최초의 알고리즘이다.

 

핵심 아이디어는 시작점에서 출발해서, 이미 최단 거리를 확정한 정점을 거쳐 다음 정점으로 가는 경로를 계속 갱신해나가는 것이다.

 

이를 점화식으로 표현하면 다음과 같다. v를 시작점, u를 현재 정점, w를 다음 정점이라고 할 때,

 

현재 알고 있는 w까지의 거리와, u를 거쳐서 w로 가는 거리를 비교해서 더 짧은 값으로 갱신한다. 이 과정을 모든 정점에 대해 반복하면 최단 경로를 얻을 수 있다.

 

하지만 다익스트라 알고리즘은 만능이 아니다. 음의 가중치가 있을 경우 올바른 최단 경로를 보장하지 못한다.

 

다음과 같은 그래프를 생각해보자.

• A → B (가중치: 5)
• B → C (가중치: 3)
• C → A (가중치: -10)

이 그래프에는 A → B → C → A라는 사이클이 존재한다. 이 사이클을 반복하면 어떻게 될까?

• 1회: 5 + 3 + (-10) = -2
• 2회: -2 + 5 + 3 + (-10) = -4
• 3회: -4 + 5 + 3 + (-10) = -6

사이클을 반복할수록 총 비용이 -2씩 줄어들어, 최단 거리는 음의 무한대로 발산한다. 즉, 음의 사이클이 있으면 "최단 거리"가 정의되지 않는다.

 

음의 가중치가 있는 그래프에서 다익스트라를 실행하면 구체적으로 어떤 일이 벌어지는지 살펴보자.

 

초반에는 정상적으로 동작하는 것처럼 보인다. 각 정점까지의 거리가 순차적으로 계산되고 확정된다. 하지만 음의 간선을 처리하는 순간, 일부 정점의 거리가 음수로 바뀐다. 문제는 이미 확정된 다른 정점들이 이 변화를 반영하지 못한다는 것이다.

 

새롭게 갱신된 음수 값은 다시 인접한 정점들의 거리를 변경해야 하고, 이 정점들이 갱신되면 또 다른 정점들도 갱신되어야 한다. 결국 계속해서 음의 사이클을 따라 값들이 갱신되며, 알고리즘이 올바른 답을 찾을 수 없게 된다.

 

따라서 다익스트라 알고리즘은 음의 가중치가 없는 그래프에서만 사용할 수 있다.

 

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

다익스트라 알고리즘은 음의 가중치가 없는 그래프에서만 사용할 수 있다는 한계가 있었다. 그렇다면 음의 가중치가 있는 그래프에서는 어떻게 최단 경로를 찾을 수 있을까?

 

벨만-포드 알고리즘은 이 문제를 해결한다. 다익스트라보다 느리지만, 음의 가중치를 처리할 수 있고 음의 사이클까지 감지할 수 있다.

 

알고리즘의 핵심 아이디어는 간단하다. 모든 간선을 반복적으로 확인하면서 거리를 갱신하는 것이다.

 

왜 이 방법이 작동할까? 최단 경로는 최대 n-1개의 간선을 거친다. 따라서 모든 간선에 대한 완화(relaxation) 작업을 n-1번 반복하면, 설령 음의 가중치가 있더라도 최단 거리를 찾을 수 있다.

 

각 반복에서 무슨 일이 일어나는지 생각해보자. 첫 번째 반복에서는 시작점에서 간선 1개로 갈 수 있는 정점들의 거리가 확정된다. 두 번째 반복에서는 간선 2개로 갈 수 있는 정점들이 확정된다. 이런 식으로 k번째 반복에서는 간선 k개로 갈 수 있는 정점들의 최단 거리가 확정된다. n-1번 반복하면 모든 정점의 최단 거리를 구할 수 있다.

 

점화식으로 표현하면 다음과 같다.

 

구체적인 예제를 통해 알고리즘의 동작을 살펴보자.

 

각 반복마다 모든 간선을 확인하면서 거리를 갱신한다. 음의 가중치가 있어도 n-1번의 반복을 거치면 올바른 최단 거리를 찾을 수 있다.

 

그렇다면 음의 사이클은 어떻게 감지할까? n-1번의 반복으로 모든 최단 거리를 찾았다면, n번째 반복에서는 더 이상 거리가 갱신되지 않아야 한다. 만약 n번째 반복에서도 거리가 줄어든다면, 이는 음의 사이클을 통해 거리가 계속 감소할 수 있다는 의미다.

 

벨만-포드의 시간복잡도는 O(VE)다. 다익스트라의 O((V+E)logV)보다 느리지만, 음의 가중치를 안전하게 처리할 수 있다는 장점이 있다.

 

5. 플로이드-워샬(Floyd-Warshall) 알고리즘

다익스트라나 벨만-포드 알고리즘은 하나의 시작점에서 다른 정점들까지의 최단 경로를 찾아준다. 그렇다면 모든 정점 쌍 사이의 최단 경로가 필요하다면 어떻게 해야 할까?

 

n개의 정점이 있는 그래프에서 모든 쌍 사이의 최단 경로는 총 n²개 존재한다. 가장 직관적인 방법은 각 정점을 시작점으로 벨만-포드 알고리즘을 n번 수행하는 것이다. 하지만 이 방법의 시간복잡도는 O(n⁴)으로 비효율적이다.

 

이 방법을 점화식으로 표현하면 다음과 같다. $d^{m}_{ij}$를 "i에서 j로 가는데 최대 m개의 간선을 사용할 때의 최단 거리"라고 정의하자. 그러면 m+1개의 간선을 사용할 때의 최단 거리는, m개의 간선으로 중간 정점 k까지 간 다음 k에서 j로 가는 경로 중 가장 짧은 것이 된다.

 

여기서 주목할 점이 있다. $d^{m}_{ij}$이 계산되면 $d^{m-1}_{ij}$은 더 이상 필요하지 않다. 따라서 3차원 배열 대신 $d_{ij}$ 변수 하나로 처리할 수 있다. 하지만 이 방법의 시간복잡도는 O(n⁴)으로 비효율적이다. n개의 정점 각각에 대해 벨만-포드 알고리즘 O(n³)을 수행하기 때문이다.

 

구체적으로 살펴보자. $d^{k}_{ij}$를 "1번부터 k번 정점까지만 경유지로 사용할 수 있을 때, i에서 j로 가는 최단 거리"라고 정의한다. 그러면

• k=0일 때: 경유지를 전혀 사용하지 않으므로, d^0_ij는 i에서 j로 가는 직접 간선의 가중치다.
• k=1일 때: 1번 정점을 거쳐갈 수 있으므로, 직접 가는 경로와 "i→1→j" 경로 중 짧은 것을 선택한다.
• k=2일 때: 1번과 2번을 거쳐갈 수 있으므로, 기존 거리와 "i→2→j" 경로를 비교한다.

k번 정점을 새로운 경유지로 추가했을 때, i에서 j로 가는 경로는 두 가지 경우로 나뉜다. 첫 번째는 k번 정점을 거치지 않는 경우로, 거리는 $d^{k-1}_{ij}$다. 두 번째는 k번 정점을 거쳐가는 경우로, 거리는 $d^{k-1}_{ik} + d^{k-1}_{kj}$다. 두 경우 중 짧은 것을 선택하면 된다.

 

 

이를 통해 시간복잡도를 O(n³)로 줄일 수 있다. 벨만-포드를 n번 수행하는 방식은 각 출발점마다 "모든 간선을 n-1번 반복 확인"해야 했지만, 플로이드-워샬은 "경유점 k 하나당 모든 쌍 (i,j)를 한 번만 확인"하면 된다.

 

각 경유점 k를 순서대로 고려하면서, 모든 정점 쌍 (i, j) 사이의 거리가 k를 거쳐가는 경로로 개선되는지 확인한다. 이 과정을 모든 정점에 대해 반복하면 최종적으로 모든 쌍 사이의 최단 거리를 얻을 수 있다.

 

플로이드-워샬 알고리즘은 음의 가중치가 있는 그래프에서도 작동한다. 하지만 음의 사이클이 존재하면 최단 거리가 정의되지 않는다. 음의 사이클의 존재는 알고리즘 실행 후 대각선 원소를 확인하여 감지할 수 있다. 만약 $d_{ii} < 0$인 정점 i가 존재한다면, i를 포함하는 음의 사이클이 존재한다는 의미다.

 

6. DAG에서의 최단 경로

지금까지 살펴본 알고리즘들은 일반적인 그래프를 다룬다. 하지만 사이클이 없는 그래프라면 어떨까?

 

사이클이 없는 유향 그래프(Directed Acyclic Graph, DAG)에서는 최단 경로를 훨씬 효율적으로 찾을 수 있다. 다익스트라나 벨만-포드 같은 복잡한 알고리즘이 필요 없다. 위상 정렬(Topological Sort)의 순서대로 정점을 방문하며 거리를 갱신하기만 하면 된다.

 

위상 정렬(topological sort)

 

왜 이것이 가능할까? DAG는 사이클이 없기 때문에, 정점들을 선형으로 나열할 수 있다. 이 순서대로 방문하면, 각 정점을 처리할 때 그 정점으로 들어오는 모든 경로가 이미 계산된 상태가 보장된다. 따라서 각 정점을 단 한 번만 방문해도 최단 거리를 정확하게 구할 수 있다.

 

알고리즘은 두 단계로 진행된다. 먼저 위상 정렬로 정점들의 방문 순서를 결정한다. 그다음 정렬된 순서대로 각 정점에서 나가는 간선을 따라 거리를 갱신한다.

 

 

거리 갱신은 다익스트라나 벨만-포드와 동일한 완화(relaxation) 방식을 사용한다.

 

구체적인 예제를 통해 알고리즘이 어떻게 작동하는지 살펴보자.

 

위상 정렬된 순서대로 정점을 방문하면서 거리를 갱신해나간다. 각 정점에서 나가는 간선들을 확인하고, 더 짧은 경로가 발견되면 거리를 업데이트한다. 사이클이 없기 때문에 역방향으로 거리가 갱신될 일이 없고, 따라서 한 번의 순회만으로 모든 최단 거리를 정확하게 계산할 수 있다.

 

시간복잡도는 O(V+E)다. 위상 정렬에 O(V+E), 거리 갱신에 O(V+E)가 소요되므로 전체적으로 선형 시간에 해결된다. 다익스트라의 O((V+E)logV)보다 빠르지만, DAG라는 제약 조건이 있을 때만 사용할 수 있다.

---

출처

쉽게 배우는 알고리즘 | 문병로 | 한빛아카데미 - 예스24