12.8 다익스트라(Dijkstra) 알고리즘

12.8 다익스트라(Dijkstra) 알고리즘

1. 알고리즘의 개요

다익스트라 알고리즘(Dijkstra’s algorithm)은 음수가 아닌 가중치를 가진 그래프에서 단일 시작점 최단 경로(Single-Source Shortest Path) 문제를 푸는 가장 표준적인 알고리즘이다. 1956년 네덜란드의 컴퓨터 과학자 에드스거 데이크스트라(Edsger W. Dijkstra)가 약 20분 만에 고안하여 1959년에 발표하였으며, 이후 컴퓨터 과학과 로봇공학의 가장 영향력 있는 알고리즘 중 하나가 되었다. 도로 네트워크의 경로 안내, 인터넷 라우팅, 로봇 경로 계획 등 광범위한 응용에서 핵심 역할을 한다.

2. 알고리즘의 핵심 아이디어

2.1 그리디 방식

다익스트라 알고리즘은 그리디(greedy) 방식이다. 매 단계마다 시작 노드에서 가장 가까운 미방문 노드를 선택하고, 그 노드를 통해 다른 노드들의 거리를 갱신한다.

2.2 거리의 단조 증가

알고리즘이 진행됨에 따라 노드들이 거리 순서로 처리된다. 이는 비가중치 그래프에서 BFS의 일반화로 볼 수 있다.

2.3 이완 연산

각 노드를 처리할 때 그 노드의 이웃들에 대해 이완(relaxation) 연산을 수행한다. 이완은 더 짧은 경로가 발견되면 거리를 갱신하는 연산이다.

3. 알고리즘의 구체적 설명

3.1 의사 코드

Dijkstra(G, s):
    // 초기화
    for each node v in G:
        v.distance = ∞
        v.parent = None
    s.distance = 0
    
    // 우선순위 큐에 모든 노드 추가
    Q = priority queue containing all nodes (key = distance)
    
    while Q is not empty:
        // 가장 가까운 미방문 노드 선택
        u = Q.extract_min()
        
        // 이웃 이완
        for each neighbor v of u:
            if v in Q:
                if v.distance > u.distance + w(u, v):
                    v.distance = u.distance + w(u, v)
                    v.parent = u
                    Q.decrease_key(v, v.distance)
    
    return distances and parents

3.2 단계별 동작

  1. 초기화: 시작 노드의 거리를 0으로, 나머지 노드의 거리를 무한대로 설정한다.
  2. 우선순위 큐: 모든 노드를 거리를 키로 한 우선순위 큐에 추가한다.
  3. 반복: 큐가 빌 때까지 다음을 반복한다.
  • 우선순위 큐에서 거리가 가장 작은 노드 u를 추출한다.
  • u의 모든 이웃 v에 대해 이완 연산을 수행한다.
  1. 종료: 모든 노드의 최단 거리가 결정되면 종료한다.

4. 알고리즘의 정확성

4.1 정리

다익스트라 알고리즘은 음수가 아닌 가중치를 가진 그래프에서 정확한 최단 거리를 계산한다.

4.2 증명 개요

알고리즘의 정확성은 다음의 주장으로 증명된다.

주장: 노드 u가 우선순위 큐에서 추출될 때, u.\text{distance}는 s에서 u로의 최단 거리이다.

이 주장은 귀납법으로 증명된다. 모순으로 가정하여 u.\text{distance}가 최단 거리가 아니라면, u로의 더 짧은 경로 P가 존재한다. P는 어떤 미방문 노드 y를 통과해야 하는데, y가 추출되지 않은 이유는 y.\text{distance} \geq u.\text{distance}이기 때문이다. 그러나 음수가 아닌 가중치이므로 P를 통한 거리는 y.\text{distance}보다 클 수 없으므로 모순이다.

4.3 음수 가중치의 문제

알고리즘의 정확성은 음수가 아닌 가중치 가정에 의존한다. 음수 가중치가 있으면 더 멀리 있는 노드를 통한 더 짧은 경로가 가능할 수 있어, 그리디 선택이 정확하지 않다.

5. 우선순위 큐의 구현

5.1 단순 배열

가장 단순한 구현은 배열을 사용하여 매번 최소값을 선형 검색하는 것이다.

  • extract_min: O(|V|)
  • decrease_key: O(1)
  • 전체 시간 복잡도: O(|V|^2)

5.2 이진 힙

이진 힙을 사용하면 더 효율적이다.

  • extract_min: O(\log|V|)
  • decrease_key: O(\log|V|)
  • 전체 시간 복잡도: O((|V| + |E|)\log|V|)

이는 가장 일반적인 구현이다.

5.3 피보나치 힙

피보나치 힙을 사용하면 이론적으로 더 효율적이다.

  • extract_min: O(\log|V|) (분할 상환)
  • decrease_key: O(1) (분할 상환)
  • 전체 시간 복잡도: O(|V|\log|V| + |E|)

다만 상수 인자가 크고 구현이 복잡하여 실제로는 잘 사용되지 않는다.

5.4 구현의 선택

그래프권장 구현
밀집 ((\vert E\vert = \Theta(\vert V\vert^2)))단순 배열
일반적인 경우이진 힙
매우 큰 희소 그래프피보나치 힙

6. 시간 복잡도와 공간 복잡도

6.1 시간 복잡도

우선순위 큐시간 복잡도
단순 배열O(\vert V\vert^2)
이진 힙O((\vert V\vert + \vert E\vert)\log\vert V\vert)
피보나치 힙O(\vert V\vert\log\vert V\vert + \vert E\vert)

6.2 공간 복잡도

다익스트라 알고리즘의 공간 복잡도는 O(|V|)이다. 거리, 부모, 우선순위 큐 모두 노드 수에 비례한다.

7. Python 구현

7.1 이진 힙 사용

Python의 heapq 모듈을 사용한 구현 예시이다.

import heapq

def dijkstra(graph, start):
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    parents = {node: None for node in graph}
    
    pq = [(0, start)]
    visited = set()
    
    while pq:
        current_distance, current_node = heapq.heappop(pq)
        
        if current_node in visited:
            continue
        visited.add(current_node)
        
        for neighbor, weight in graph[current_node].items():
            if neighbor in visited:
                continue
            
            new_distance = current_distance + weight
            if new_distance < distances[neighbor]:
                distances[neighbor] = new_distance
                parents[neighbor] = current_node
                heapq.heappush(pq, (new_distance, neighbor))
    
    return distances, parents

7.2 경로 재구성

def reconstruct_path(parents, start, end):
    path = []
    current = end
    while current is not None:
        path.append(current)
        current = parents[current]
    path.reverse()
    if path[0] != start:
        return None  # 경로 없음
    return path

8. 다익스트라의 변형

8.1 양방향 다익스트라

양방향 다익스트라(bidirectional Dijkstra)는 시작 노드와 목표 노드에서 동시에 다익스트라를 시작한다. 두 검색이 만나는 점에서 종료한다. 검색 공간을 크게 줄인다.

8.2 다중 시작점 다익스트라

여러 시작 노드에서 동시에 다익스트라를 시작할 수 있다. 모든 노드까지의 가장 가까운 시작 노드의 거리를 계산한다.

def multi_source_dijkstra(graph, sources):
    distances = {node: float('inf') for node in graph}
    pq = []
    for source in sources:
        distances[source] = 0
        heapq.heappush(pq, (0, source))
    
    while pq:
        current_distance, current_node = heapq.heappop(pq)
        if current_distance > distances[current_node]:
            continue
        for neighbor, weight in graph[current_node].items():
            new_distance = current_distance + weight
            if new_distance < distances[neighbor]:
                distances[neighbor] = new_distance
                heapq.heappush(pq, (new_distance, neighbor))
    
    return distances

8.3 차단 다익스트라

목표 노드를 알고 있다면, 목표 노드를 처리하는 즉시 종료할 수 있다. 이는 검색 시간을 단축한다.

def dijkstra_to_target(graph, start, target):
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    parents = {node: None for node in graph}
    pq = [(0, start)]
    visited = set()
    
    while pq:
        current_distance, current_node = heapq.heappop(pq)
        
        if current_node == target:
            return reconstruct_path(parents, start, target)
        
        if current_node in visited:
            continue
        visited.add(current_node)
        
        for neighbor, weight in graph[current_node].items():
            if neighbor in visited:
                continue
            new_distance = current_distance + weight
            if new_distance < distances[neighbor]:
                distances[neighbor] = new_distance
                parents[neighbor] = current_node
                heapq.heappush(pq, (new_distance, neighbor))
    
    return None

9. 다익스트라와 BFS

9.1 비교

측면BFSDijkstra
그래프비가중치음수가 아닌 가중치
자료 구조큐우선순위 큐
처리 순서레벨 순서거리 순서
시간 복잡도O(\vert V\vert + \vert E\vert)O((\vert V\vert + \vert E\vert)\log\vert V\vert)

9.2 일반화

다익스트라는 BFS의 일반화로 볼 수 있다. 모든 엣지의 가중치가 1이면 다익스트라가 BFS와 동등하다.

10. 다익스트라와 A*

10.1 비교

측면DijkstraA*
휴리스틱사용 안 함사용
효율성균등 탐색목표 지향 탐색
단일 시작점지원일반적으로 단일 쌍
최적성항상 보장수용성 휴리스틱 시 보장

10.2 A*로의 일반화

A* 알고리즘은 다익스트라에 휴리스틱을 추가한 것으로 볼 수 있다. 휴리스틱이 0이면 A*는 다익스트라와 같다.

11. 음수 가중치의 처리

11.1 다익스트라의 한계

다익스트라는 음수 가중치를 처리할 수 없다. 음수 가중치가 있으면 다음과 같은 문제가 발생한다.

  • 그리디 선택이 정확하지 않다.
  • 처리된 노드의 거리가 후에 더 짧아질 수 있다.

11.2 대안

음수 가중치가 있는 경우 다음의 알고리즘을 사용한다.

  • Bellman-Ford: 음수 가중치를 처리하고 음수 사이클을 검출한다.
  • Johnson: 음수 가중치를 양수로 변환한 후 다익스트라를 적용한다.

12. 최적화 기법

12.1 인덱스 우선순위 큐

decrease_key 연산이 효율적인 인덱스 우선순위 큐를 사용하면 더 효율적이다.

12.2 게으른 삭제

이미 처리된 노드를 큐에서 삭제하지 않고, 추출 시 검사하는 게으른 삭제 전략이 단순하고 효율적이다.

while pq:
    current_distance, current_node = heapq.heappop(pq)
    if current_distance > distances[current_node]:
        continue  # 이미 더 짧은 경로 발견
    # ... 처리

12.3 그래프의 전처리

도로 네트워크와 같은 큰 그래프에서는 전처리를 통해 다익스트라를 가속할 수 있다. 계층적 접근법(예: Contraction Hierarchies, ALT)이 사용된다.

13. 응용

13.1 도로 네트워크의 경로 안내

도로 네트워크의 GPS 내비게이션은 다익스트라 또는 그 변형을 사용한다. 거리, 시간, 연료 비용 등을 가중치로 사용할 수 있다.

13.2 인터넷 라우팅

OSPF(Open Shortest Path First)와 같은 라우팅 프로토콜은 다익스트라를 사용한다. 각 라우터가 네트워크의 최단 경로를 계산한다.

13.3 지연 분석

회로 설계, 통신 네트워크 등에서 신호 지연을 분석할 때 다익스트라가 사용된다.

13.4 로봇공학

모바일 로봇의 경로 계획, 매니퓰레이터의 운동 계획, 자율 주행 차량의 경로 결정 등에서 다익스트라가 활용된다.

14. 로봇공학에서의 응용

14.1 격자 경로 계획

격자 환경에서 다익스트라는 균등 비용 검색을 수행한다. 비용이 거리에 따라 변할 때 효과적이다.

def grid_dijkstra(grid, start, goal):
    rows, cols = len(grid), len(grid[0])
    distances = {}
    pq = [(0, start)]
    parents = {start: None}
    
    while pq:
        d, (r, c) = heapq.heappop(pq)
        if (r, c) == goal:
            return reconstruct_path(parents, start, goal)
        if (r, c) in distances:
            continue
        distances[(r, c)] = d
        
        for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] != 1:
                if (nr, nc) not in distances:
                    new_d = d + grid[nr][nc]  # 셀의 비용
                    heapq.heappush(pq, (new_d, (nr, nc)))
                    parents[(nr, nc)] = (r, c)
    
    return None

14.2 매니퓰레이터의 운동 계획

매니퓰레이터의 구성 공간에 PRM(Probabilistic Roadmap)을 구축한 후 다익스트라로 경로를 찾는다.

14.3 자율 주행

자율 주행 차량의 경로 계획에서 도로 네트워크의 다익스트라가 기본이다. 실시간 교통 정보가 가중치에 반영된다.

14.4 다중 로봇 경로 계획

다중 로봇이 협력하여 경로를 계획할 때, 각 로봇에 대해 다익스트라가 적용될 수 있다. 충돌 회피는 추가 제약으로 처리된다.

15. 응용 예시: 도로 네트워크의 최단 경로

서울에서 부산까지의 최단 경로를 찾는 문제를 생각해 보자. 도로 네트워크는 거대한 가중치 그래프이며, 노드는 교차로, 엣지는 도로 구간이다. 가중치는 거리 또는 통과 시간이다.

다익스트라가 직접 적용될 수 있지만, 도로 네트워크의 크기 때문에 효율성이 중요하다. Contraction Hierarchies와 같은 전처리 기법이 사용된다.

16. 응용 예시: 청소 로봇

청소 로봇이 방의 시작 위치에서 충전 도크까지 가장 효율적으로 이동할 때 다익스트라가 사용된다. 각 셀의 비용은 표면의 거칠기, 장애물 가까움 등을 반영할 수 있다.

17. 응용 예시: 매니퓰레이터의 운동 계획

매니퓰레이터의 구성 공간에서 PRM이 노드(자세)와 엣지(가능한 운동)로 그래프를 구축한다. 시작 자세에서 목표 자세까지의 가장 부드러운 경로를 다익스트라로 찾는다.

18. 응용 예시: 자율 주행 시뮬레이션

자율 주행 차량의 시뮬레이션에서 다익스트라가 경로 계획의 기준 알고리즘으로 사용된다. 다양한 도로 조건에서의 성능이 평가된다.

19. 응용 예시: 게임의 캐릭터 이동

게임에서 NPC(Non-Player Character)가 목표 위치로 이동할 때 다익스트라 또는 A*가 사용된다.

20. 다익스트라의 라이브러리 지원

20.1 NetworkX

import networkx as nx

G = nx.Graph()
G.add_weighted_edges_from([(1, 2, 0.5), (1, 3, 1.2), (2, 3, 0.3), (2, 4, 1.5)])

# 모든 노드까지의 거리
distances = nx.single_source_dijkstra_path_length(G, source=1)
print(distances)  # {1: 0, 2: 0.5, 3: 0.8, 4: 2.0}

# 특정 노드까지의 경로
path = nx.dijkstra_path(G, source=1, target=4)
print(path)  # [1, 2, 4]

20.2 다른 라이브러리

  • igraph
  • Boost Graph Library
  • graph-tool
  • Google OR-Tools

21. 학습의 가치

다익스트라 알고리즘을 깊이 이해하는 것은 다음과 같은 이점을 제공한다.

  • 가장 중요한 그래프 알고리즘 중 하나를 익힌다.
  • 그리디 알고리즘 설계의 표본을 학습한다.
  • 우선순위 큐의 활용을 익힌다.
  • 로봇 경로 계획의 기본 도구를 습득한다.
  • 더 고급 알고리즘(A*, Bellman-Ford, Johnson)의 기초를 형성한다.

22. 학습 권장사항

22.1 직접 구현

다익스트라를 처음부터 직접 구현해 보는 것이 중요하다. 우선순위 큐를 사용한 효율적인 구현을 익힌다.

22.2 시각화

다익스트라의 단계별 시각화는 알고리즘의 동작을 이해하는 데 매우 유용하다. 각 단계에서 거리가 어떻게 갱신되는지 볼 수 있다.

22.3 응용 학습

격자 환경의 경로 계획, 도로 네트워크의 최단 경로 등 실제 응용에 적용해 본다.

22.4 변형 학습

양방향 다익스트라, 다중 시작점 다익스트라, 차단 다익스트라 등의 변형을 학습한다.

23. 알고리즘의 한계와 개선

23.1 한계

  • 음수 가중치를 처리할 수 없다.
  • 매우 큰 그래프에서는 효율성이 부족할 수 있다.
  • 동적 그래프에 대한 처리가 어렵다.

23.2 개선

  • A*: 휴리스틱을 사용한 효율적인 단일 쌍 최단 경로
  • Contraction Hierarchies: 도로 네트워크의 전처리
  • ALT: 랜드마크 기반 가속
  • Bidirectional Dijkstra: 양방향 검색
  • Dynamic Dijkstra: 동적 그래프 처리

24. 본 절의 의의

본 절은 다익스트라 알고리즘을 자세히 다루었다. 이는 가장 영향력 있는 그래프 알고리즘 중 하나이며, 로봇공학을 포함한 다양한 분야에서 광범위하게 활용된다. 다익스트라의 이해는 더 고급 알고리즘 학습의 기반이 된다.

25. 참고 문헌

  • Dijkstra, E. W. (1959). “A note on two problems in connexion with graphs.” Numerische Mathematik, 1(1), 269–271.
  • Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
  • Sedgewick, R., & Wayne, K. (2011). Algorithms (4th ed.). Addison-Wesley.
  • Sniedovich, M. (2006). “Dijkstra’s algorithm revisited: the dynamic programming connexion.” Control and Cybernetics, 35(3), 599–620.
  • Geisberger, R., Sanders, P., Schultes, D., & Delling, D. (2008). “Contraction hierarchies: Faster and simpler hierarchical routing in road networks.” International Workshop on Experimental and Efficient Algorithms, 319–333.
  • Skiena, S. S. (2008). The Algorithm Design Manual (2nd ed.). Springer.

version: 1.0