[Algorithm] 다익스트라 알고리즘 (Dijkstra algorithm)

현실 세계에서 우리는 종종 어떤 출발지에서 목적지까지 가장 빠른 길, 가장 저렴한 경로, 혹은 가장 짧은 통신 경로를 찾아야 할 때가 있다. 이런 문제들은 그래프라는 수학적 구조로 표현할 수 있다. 그래프는 정점(노드)과 간선(정점 간 연결선)으로 구성되며, 간선은 이동에 필요한 비용, 거리, 시간 같은 가중치를 가진다. 그래프는 유방향(방향이 있는 간선)일 수도 있고, 무방향(양쪽으로 이동 가능한 간선)일 수도 있다. 다익스트라 알고리즘은 둘 모두에 적용할 수 있으며, 무방향 그래프에서는 각 간선을 양 방향 모두 등록해야 한다. 예를 들어, \( u \)와 \( v \) 사이에 간선이 있다면, \( u \to v \), \( v \to u \) 모두 추가해주어야 다익스트라 알고리즘이 정상 동작한다.

문제는 복잡한 네트워크 안에서 단순히 한두 개의 경로를 찾는 것이 아니라, 출발지로부터 모든 정점까지의 최적 경로를 효율적으로 찾아야 한다는 점이다. 그리고 이 최적 경로를 찾을 때 가장 널리 사용되는 알고리즘 중 하나가 바로 다익스트라 알고리즘(Dijkstra's Algorithm) 이다.

 

다익스트라 알고리즘의 기본 사고방식

다익스트라는 아주 직관적인 생각을 기반으로 한다. 출발지에서 가까운 곳은 빠르게 도달할 수 있을 것이고, 먼 곳은 그만큼 더 시간이 걸릴 것이라는 당연한 생각이다. 그래서 다익스트라는 출발지로부터 거리를 하나하나 늘려가며 가장 짧은 경로를 차례차례 확정해 나간다.

중요한 점은 이 확정의 기준이다. 아직 방문하지 않은 정점들 중에서 현재까지 알려진 거리(최소 비용)가 가장 짧은 정점을 매번 선택해서 다음 경로를 확장한다. 이 방식은 일종의 "탐욕적 방법" (Greedy Strategy)이다. 즉, 현재 상황에서 가장 좋아 보이는 선택을 계속한다는 뜻이다.

 

다익스트라 알고리즘이 제대로 작동하려면

여기서 매우 중요한 전제가 있다. 간선의 가중치가 절대 음수가 되어서는 안 된다는 점이다. 왜냐하면, 음수 가중치가 있으면, 나중에 어떤 경로를 돌아서 가는 것이 오히려 비용이 더 줄어드는 경우가 생길 수 있기 때문이다. 다익스트라는 "한 번 최단 경로가 확정된 정점은 다시 고려할 필요 없다"고 생각하며 진행하는데, 이 전제가 깨지는 순간 알고리즘 전체가 무너진다.

예를 들어, 시작점 A에서 정점 B까지 거리가 3으로 확정되었는데, 나중에 어떤 음수 가중치 경로를 통해 1로 줄어든다면? 다익스트라는 그걸 감지할 수 없다. 그래서 음수 가중치가 허용되는 경우에는 다익스트라 대신 벨만-포드 알고리즘처럼 다른 알고리즘을 사용해야 한다.

수학적으로 다익스트라 알고리즘이 풀고자 하는 문제는 다음과 같다.

- 주어진 그래프 \( G = (V, E) \)가 있다.
  - \( V \): 정점들의 집합
  - \( E \): 간선들의 집합
- 각 간선 \( (u, v) \in E \)에는 양의 가중치 \( w(u, v) \geq 0 \)가 주어진다.

주어진 시작점 \( s \in V \)로부터 다른 모든 정점 \( v \in V \)까지의 최단 거리 \( d(s, v) \)를 구하는 것이다.  
여기서 최단 거리란, 출발지 \( s \)로부터 정점 \( v \)까지 도달 가능한 경로들 중, 간선들의 가중치 합이 최소가 되는 경로를 의미한다.

이를 수학적으로 표현하면 다음과 같다:
\[
d(s, v) = \min_{p \in P(s, v)} \sum_{(u, v) \in p} w(u, v)
\]
- \( P(s, v) \): 출발점 \( s \)에서 정점 \( v \)까지 가는 모든 경로 집합

 

알고리즘의 실제 동작 과정

이제 다익스트라 알고리즘이 실제로 어떻게 동작하는지 살펴보자. 먼저 출발점의 거리를 0으로 초기화하고, 나머지 모든 정점의 거리를 무한대로 설정한다. 무한대란 아직 그 정점까지 가는 경로를 모르겠다는 뜻이다.

처음에는 출발점 하나만 알고 있으므로, 이 정점을 기준으로 연결된 이웃 정점들의 거리를 계산한다. 만약 어떤 경로를 통해 이웃 정점에 도달할 수 있고, 그 거리가 현재 기록된 거리보다 짧다면, 그 값을 갱신한다.

그 다음에는 아직 방문하지 않은 정점들 중에서, 현재까지 거리 값이 가장 작은 정점을 선택한다. 그리고 이 정점을 기준으로 다시 이웃 정점들의 거리를 갱신한다. 이 과정을 모든 정점이 처리될 때까지 반복한다.

매번 가장 거리가 가까운 정점을 빨리 찾기 위해 우선순위 큐(힙 구조)를 사용한다. 힙을 사용하면 다음으로 최단 거리를 가진 정점을 찾고 제거하는 데 \( O(\log V) \) 시간이 걸린다.

 

처음에, 우리는 출발점 \( s \)를 제외한 모든 정점들의 거리를 무한대(\( \infty \))로 설정한다. 출발점은 0으로 설정한다.

초기화:
\[
\text{dist}(v) =
\begin{cases}
0, & \text{if } v = s \\
\infty, & \text{otherwise}
\end{cases}
\]
그리고 아직 아무 정점도 방문하지 않았으므로, 방문 집합 \( S = \emptyset \)이다.
우선순위 큐 \( Q \)를 준비하여 (거리, 정점) 쌍을 관리한다.

 

다익스트라 알고리즘은 기본적으로 다음 세 가지 단계로 구성된다:

1. 거리 배열을 무한대로 초기화하고, 출발 노드의 거리를 0으로 설정

INF = 10**18
dist = [INF] * 노드개수
dist[출발노드] = 시작비용

 

2. 우선순위 큐에 (거리, 정점) 쌍을 삽입

pq = [(dist[출발노드], 출발노드)]

 

3. 큐에서 꺼낸 정점을 기준으로 인접 정점들을 완화(relaxation)

아래 코드는 큐에 (현재까지 거리, 노드 번호) 쌍을 저장하고, 큐에서 꺼낸 노드에 대해 현재 거리가 최신 거리인지 검사한 뒤 진행한다. 이처럼 큐에 같은 노드가 여러 번 들어가는 것을 허용하고, 꺼낼 때마다 검사하는 방식을 흔히 느슨한 다익스트라(Loose Dijkstra) 라고 부른다.

while pq:
    cur_cost, u = heapq.heappop(pq)
    if cur_cost > dist[u]:
        continue
    for v, w in graph[u]:
        nd = cur_cost + w
        if nd < dist[v]:
            dist[v] = nd
            heapq.heappush(pq, (nd, v))

 

느슨한 방식은 큐에 무조건 삽입하고 꺼낼 때 검사를 하기 때문에 로직 구조가 단순하지만, 큐에 중복된 노드가 들어갈 수 있어 큐 크기가 커질 수 있다. 한편, 큐에 항상 최신 거리만 삽입하는 엄격한 방식으로도 구현할 수 있다. 엄격한 방식에서는 삽입 전에 거리 조건을 확인하여, 더 좋은 경로를 찾았을 때만 큐에 삽입한다.

while pq:
    cur_cost, u = heapq.heappop(pq)
    for v, w in graph[u]:
        if dist[v] > cur_cost + w:
            dist[v] = cur_cost + w
            heapq.heappush(pq, (dist[v], v))

 

엄격한 방식은 중복 삽입이 줄어들어 큐 메모리 사용량이 절약되지만, 삽입할 때마다 추가적인 조건 검사를 해줘야 한다.

 

위 기본 구조를 조금 더 자세히 풀어보면 다음과 같은 반복 과정을 거치게 된다:
1. 큐 \( Q \)에서 거리값이 가장 작은 정점인 최단 거리 후보 \( u \)를 꺼낸다.
2. \( u \)를 방문 집합 \( S \)에 추가한다.
3. \( u \)에 인접한 모든 정점 \( v \)에 대해:
    - 새로운 거리 후보 계산:
    \[
    \text{alt} = \text{dist}(u) + w(u, v)
    \]
    - 만약 \( \text{alt} < \text{dist}(v) \)라면:
        - \( \text{dist}(v) = \text{alt} \)
        - 큐 \( Q \)에 새로운 거리 값을 삽입한다.

이 과정을 모든 정점에 대해 반복하면, \( \text{dist}(v) \)는 출발점 \( s \)로부터 정점 \( v \)까지의 최단 거리가 된다.

 

 

수학적 보증

왜 다익스트라 방식이 "올바른 최단 경로"를 보장할 수 있을까?
그 이유는 다음과 같다.

• 가장 먼저 처리하는 정점은 항상, 출발지로부터 현재까지 갈 수 있는 가장 짧은 거리를 가진다.
• 가중치가 양수이기 때문에, 한 번 확정된 거리는 더 이상 줄어들 수 없다.
• 따라서 매번 가장 짧은 거리를 확정해 나가면 전체 경로가 틀릴 일이 없다.

이 논리는 수학적으로 귀납법(Induction)을 통해 증명할 수 있다. 처음에는 출발지의 거리가 0으로 맞고, 그 다음으로 거리가 짧은 정점을 확정할 때도 그보다 더 짧은 경로는 존재할 수 없음을 수학적으로 보일 수 있다.

 

시간 복잡도와 효율성

다익스트라 알고리즘의 시간 복잡도는 사용한 자료구조에 따라 달라진다.

• 간단한 배열을 사용한다면 \( O(V^2) \)이다. 매번 모든 정점 중 최소 거리를 찾는 데 \( O(V) \)가 걸리기 때문이다.
• 그러나 우선순위 큐(힙)를 사용하면, 복잡도는 \( O((V+E)\log V) \)로 줄어든다. 힙에서 삽입, 삭제가 \( O(\log V) \)로 빠르게 동작하기 때문이다.

 

다익스트라 알고리즘의 한계

다익스트라는 아주 강력하지만, 두 가지 큰 약점이 있다.

첫째, 앞서 말했듯이 음수 가중치에서는 사용할 수 없다.
둘째, 모든 정점에 대해 거리를 계산하므로, 필요한 정점만 최적화해서 찾는 상황(예: 특정 목적지 하나만 찾는 경우)에서는 A* 알고리즘처럼 추가적인 휴리스틱이 들어간 방법이 더 효율적일 수 있다.

참고로, 다익스트라는 "하나의 시작점에서 다른 모든 정점까지의 최단 경로"를 구하는 알고리즘이다.
만약 모든 정점 쌍 간의 최단 경로를 구해야 한다면, 다익스트라 알고리즘만으로는 비효율이며, 이럴 때 사용하는 방법이 바로 플로이드-워셜 알고리즘(Floyd-Warshall Algorithm) 이다

 

플로이드-워셜 알고리즘

플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)은 그래프 내 모든 정점 쌍 간의 최단 경로를 한 번에 구하는 알고리즘이다.

다익스트라 알고리즘이 하나의 출발점에서 다른 모든 정점까지의 최단 거리를 구하는 데에 초점을 맞춘다면, 플로이드-워셜은 모든 정점끼리 이동할 때의 최단 거리를 전부 계산한다.

• 경유지를 하나씩 추가해가면서 "거쳐서 가는 경로가 더 짧은지"를 점검하고, 최단 거리를 갱신한다.
• 즉, 정점 \( k \)를 중간에 거쳤을 때, \( i \to j \)로 가는 비용이 줄어드는지 확인하고, 줄어든다면 갱신한다.
• 이 과정을 모든 정점 \( k \)에 대해 반복한다.

수식으로 표현하면 다음과 같다:
$$
\text{dist}(i, j) = \min(\text{dist}(i, j),\ \text{dist}(i, k) + \text{dist}(k, j))
$$

• 여기서 \( \text{dist}(i, j) \)는 정점 \( i \)에서 정점 \( j \)까지의 최단 거리다.
• 이 식을 모든 \( i, j, k \)에 대해 세 번 반복하면 모든 최단 경로가 구해진다.

이에 대한 특징은:

• 시간 복잡도는 \( O(V^3) \)로, 정점 수가 적을 때 적합하다.
• 다익스트라가 간선 개수에 비례하는 복잡도를 갖는 데 비해, 플로이드-워셜은 정점 수만을 기준으로 삼는다.
• 음수 가중치가 있는 경우도 안전하게 사용할 수 있다. (단, 음수 사이클이 있다면 별도로 감지해야 한다.)

 

정리하면, 다익스트라 알고리즘은 "탐욕적 선택"과 "우선순위 큐"를 결합하여 출발지로부터 다른 모든 정점까지의 최단 거리를 계산하는 강력한 방법이다.
단, 간선 가중치가 모두 0 이상이어야 하고, 모든 정점까지 거리를 구하는 데 시간이 꽤 걸릴 수 있다.
하지만 명확하고 안정적인 특성 덕분에 현실 세계의 수많은 경로 탐색, 네트워크 분석, 지도 애플리케이션에 널리 쓰이고 있다.

 

 

출처: Wikipedia, "데이크스트라 알고리즘", 링크