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

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

1. 다익스트라 알고리즘 개요

다익스트라 알고리즘은 그래프의 한 정점(Vertex)에서 다른 모든 정점까지의 최단 경로(Shortest Path)를 찾는 알고리즘으로, 가중치(Weight)가 음수가 아닌 그래프에서 사용됩니다.

일상생활에서 내비게이션이 최적의 경로를 찾아주거나, 네트워크 라우팅 프로토콜이 가장 효율적인 데이터 전송 경로를 결정하는 등 다양한 분야에서 활용되는 핵심적인 알고리즘입니다.

---

2. 이론

2.1. 기본 개념

다익스트라 알고리즘은 탐욕 알고리즘(Greedy Algorithm) 에 기반합니다. 각 단계에서 현재까지 계산된 최단 거리를 기준으로, 방문하지 않은 정점 중 가장 거리가 짧은 정점을 선택하고, 해당 정점을 거쳐가는 경로가 기존 경로보다 더 짧은지를 검사하여 거리(비용) 테이블을 갱신하는 과정을 반복합니다.

• 정점(Vertex/Node): 그래프의 각 지점 (예: 도시, 교차로)
• 간선(Edge): 정점들을 연결하는 선 (예: 도로, 네트워크 회선)
• 가중치(Weight): 간선에 부여된 값 (예: 거리, 시간, 비용)
• 시작 정점: 최단 경로 탐색을 시작할 기준 정점
• 거리 테이블(Distance Table): 시작 정점으로부터 각 정점까지의 현재까지 알려진 최단 거리를 저장하는 배열 또는 해시 테이블. 처음에는 시작 정점은 0, 나머지는 무한대(Infinity)로 초기화됩니다.
• 방문한 정점 집합: 최단 거리가 확정된 정점들의 집합.

2.2. 내부 구조 및 구현 방식

2.2.1. 알고리즘 동작 과정

1. 초기화:
   • 시작 정점에서 모든 다른 정점까지의 거리를 저장할 distances 배열을 생성하고, 시작 정점의 거리는 0으로, 나머지는 모두 무한(∞)으로 초기화합니다.
   • 방문한 정점을 기록할 visited 배열을 false로 초기화합니다.
   • 모든 정점을 담을 자료구조(주로 우선순위 큐)를 준비하고, 시작 정점을 {거리: 0, 정점: 시작정점} 형태로 넣습니다.
2. 반복:
   • distances 배열(또는 우선순위 큐)에서 아직 방문하지 않은 정점 중 가장 거리가 짧은 정점 u를 선택합니다.
   • 정점 u를 방문 처리합니다 (visited[u] = true).
   • 정점 u와 인접한 모든 정점 v에 대해 다음을 검사합니다.
     • u를 거쳐 v로 가는 새로운 경로의 거리(distances[u] + weight(u, v))가 기존에 알려진 v까지의 거리(distances[v])보다 짧다면, distances[v]를 새로운 값으로 갱신합니다.
     • 우선순위 큐를 사용하는 경우, 갱신된 거리와 함께 v를 큐에 추가합니다.
3. 종료:
   • 모든 정점을 방문했거나, 우선순위 큐가 비어있으면 알고리즘이 종료됩니다.
   • 최종적으로 distances 배열에는 시작 정점으로부터 각 정점까지의 최단 거리가 저장됩니다.

2.2.2. 핵심 자료구조: 우선순위 큐 (Priority Queue)

다익스트라 알고리즘의 성능은 "방문하지 않은 정점 중 가장 거리가 짧은 정점을 찾는" 과정을 얼마나 효율적으로 수행하는지에 따라 결정됩니다.

• 단순 배열/리스트 사용 시:
  • 매 단계마다 distances 배열 전체를 선형 탐색하여 최솟값을 찾아야 합니다.
  • 이 과정의 시간 복잡도는 O(V)이며, V개의 정점에 대해 반복하므로 총 시간 복잡도는 O(V²) 가 됩니다.
  • 그래프가 밀집(Dense Graph, 간선 수가 V²에 가까움)할 경우 효율적일 수 있습니다.
• 우선순위 큐 (최소 힙) 사용 시:
  • 우선순위 큐는 항상 가장 작은 값을 가진 원소를 O(log V) 시간 복잡도로 추출할 수 있게 해주는 자료구조입니다.
  • 알고리즘 시작 시, 시작 정점을 우선순위 큐에 넣습니다.
  • 매 단계에서 큐에서 가장 거리가 짧은 정점을 O(log V)만에 꺼냅니다.
  • 인접 정점의 거리를 갱신할 때, 해당 정점을 큐에 넣는 작업 역시 O(log V)가 걸립니다.
  • 모든 정점은 한 번씩 큐에서 추출되고(V * log V), 모든 간선에 대해 한 번씩 거리 갱신이 일어날 수 있으므로(E * log V), 총 시간 복잡도는 O((V + E) log V) 또는 간선이 정점보다 항상 많으므로 O(E log V) 로 표현됩니다.
  • 그래프가 희소(Sparse Graph, 간선 수가 V에 가까움)할 경우 O(V²) 방식보다 훨씬 효율적입니다. 현대의 대부분 응용(도로망, 네트워크 등)은 희소 그래프에 해당합니다.

2.3. 다른 최단 경로 알고리즘과의 비교

특징	다익스트라 (Dijkstra)	벨만-포드 (Bellman-Ford)	A* (A Star)	플로이드-워셜 (Floyd-Warshall)
목표	하나의 시작 정점에서 모든 다른 정점까지의 최단 경로	하나의 시작 정점에서 모든 다른 정점까지의 최단 경로	하나의 시작 정점에서 하나의 목표 정점까지의 최단 경로	모든 정점 쌍 간의 최단 경로
음수 가중치	허용 안 함	허용함 (음수 사이클 감지 가능)	허용 안 함 (휴리스틱 함수에 따라 다름)	허용함 (음수 사이클 감지 가능)
시간 복잡도	O(E log V) (우선순위 큐 사용 시)	O(VE)	다익스트라와 유사하나 휴리스틱 성능에 따라 더 빠를 수 있음	O(V³)
핵심 아이디어	탐욕적(Greedy)으로 가장 가까운 정점을 먼저 방문	모든 간선에 대해 (V-1)번의 완화(Relaxation) 작업을 반복	다익스트라 + 목표 정점까지의 예상 거리(휴리스틱) 사용	동적 계획법(Dynamic Programming) 기반
주 사용처	음수 가중치가 없는 일반적인 최단 경로 문제 (내비게이션, 라우팅)	음수 가중치가 존재하거나 음수 사이클 감지가 필요한 경우	게임 NPC 길찾기, 실시간 경로 탐색 등 목표가 명확한 경우	모든 정점 간의 거리를 미리 계산해둬야 할 때 (경유지 찾기)

• 다익스트라 vs 벨만-포드: 다익스트라는 음수 가중치를 처리하지 못합니다. 왜냐하면 한 번 방문한 정점은 최단 거리가 '확정'되었다고 가정하는데, 나중에 발견된 음수 가중치 간선 때문에 이 가정이 깨질 수 있기 때문입니다. 반면 벨만-포드는 매번 모든 간선을 확인하며 거리를 갱신하므로 음수 가중치를 처리할 수 있고, V번째 반복에서 거리가 또 갱신된다면 음수 사이클이 존재한다고 판별할 수 있습니다.
• 다익스트라 vs A*: A는 다익스트라의 확장판으로 볼 수 있습니다. 다익스트라가 f(n) = g(n) (시작점에서 현재 정점까지의 거리)을 기준으로 다음 정점을 선택한다면, A는 f(n) = g(n) + h(n) (시작점에서 현재 정점까지의 거리 + 현재 정점에서 목표 정점까지의 추정 거리)을 사용합니다. 이 휴리스틱(heuristic) h(n) 덕분에 목표 방향으로 더 빠르게 탐색을 진행할 수 있습니다.

---

3. 동작 계층 구조

다익스트라 알고리즘이 실제 애플리케이션에서 어떻게 동작하는지 계층별로 살펴보면 다음과 같습니다.

1. 사용자 영역 (User Space)
   • 애플리케이션: 사용자가 내비게이션 앱에서 'A지점'에서 'B지점'까지의 최단 경로를 요청합니다.
   • 입력: 출발지(A), 목적지(B) 좌표 또는 주소.
2. 애플리케이션 계층 (Application Layer)
   • 서비스 로직: 사용자 요청을 받아, 지도 데이터베이스에서 출발지와 목적지에 가장 가까운 도로 위의 노드(교차로 등)를 찾습니다.
   • 그래프 모델링: 전체 도로망 데이터를 바탕으로 필요한 영역의 그래프를 생성합니다.
     • 교차로, 분기점 → 정점 (Node)
     • 도로 → 간선 (Edge)
     • 도로의 길이, 예상 통행 시간 → 가중치 (Weight)
   • 알고리즘 호출: 생성된 그래프 모델과 시작 정점을 인자로 하여 다익스트라 알고리즘 함수를 호출합니다.
3. 알고리즘 및 자료구조 계층 (Algorithm & Data Structure Layer)
   • 다익스트라 알고리즘이 실행됩니다.
   • 자료구조:
     • 그래프는 인접 리스트(Adjacency List)로 표현되는 경우가 많습니다. 특정 교차로에서 연결된 다른 교차로들과 그 사이의 도로(가중치) 정보를 효율적으로 저장합니다.
     • 우선순위 큐(Priority Queue)가 (거리, 정점) 쌍을 저장하며, 다음으로 탐색할 가장 가까운 정점을 빠르게 찾아냅니다.
   • 계산: 알고리즘 로직에 따라 거리 테이블이 계속 갱신됩니다.
   • 결과 반환: 시작 정점부터 모든 다른 정점까지의 최단 거리 정보와, 경로를 역추적할 수 있는 정보(각 정점이 어떤 이전 정점으로부터 갱신되었는지)를 애플리케이션 계층에 반환합니다.
4. 시스템/커널 계층 (System/Kernel Space)
   • 프로세스 실행: 다익스트라 알고리즘 코드는 서버의 CPU에서 연산을 수행하는 프로세스로 실행됩니다.
   • 메모리 관리: 운영체제는 그래프 데이터, 우선순위 큐, 거리 테이블 등을 저장할 메모리(RAM) 공간을 할당하고 관리합니다.
   • I/O: 만약 그래프 데이터가 매우 커서 파일이나 데이터베이스에 저장되어 있다면, 파일 시스템 I/O 또는 네트워크 I/O를 통해 데이터를 읽어오는 작업이 이 계층에서 처리됩니다.

---

4. 요약

다익스트라 알고리즘은 어떤 한 지점에서 다른 모든 지점까지 가는 가장 빠른 길을 찾는 방법이라고 생각하시면 됩니다. 예를 들어, 내비게이션에서 저희 집부터 회사까지 가장 빨리 가는 길을 찾을 때 이와 같은 알고리즘이 사용됩니다.

동작 방식은, 먼저 출발점 바로 옆에 있는 길들 중 가장 가까운 곳을 '최단 경로' 후보로 정합니다. 그리고 그 후보 지점에서 또 연결된 다른 길들을 살펴보면서, 출발점에서부터의 총 거리를 계속 계산하고 기록해 나갑니다. 이 과정을 반복하면서, 이전에 찾았던 길보다 더 빠른 새로운 길이 나타나면 그 정보로 계속 바꿔주는(갱신하는) 겁니다.

이때 '다음엔 어디를 살펴볼까?'를 결정하기 위해 '우선순위 큐'라는 도구를 쓰면 훨씬 빨라지는데, 이건 항상 가장 가까운 후보지를 바로 알려주는 편리한 장바구니 같은 역할을 합니다.