다익스트라 알고리즘, 최단 경로를 시각적으로 이해하기
by DD
3개월 전
조회수 24
다익스트라 알고리즘(Dijkstra's Algorithm)은 가중치가 있는 방향 그래프(Edge-weighted Digraph)에서 단일 시작점으로부터 다른 모든 정점까지의 최단 경로를 찾는 알고리즘이다.
알고리즘은 최단 경로 트리(Shortest-Paths Tree, SPT)를 구축하며, 각 정점까지의 최단 거리와 해당 경로의 마지막 간선을 저장한다.
알고리즘의 핵심은 간선 완화(Edge Relaxation) 연산이며, 우선순위 큐(Priority Queue)를 사용하여 최단 거리를 가진 정점을 선택한다.
알고리즘의 정확성은 두 가지 불변성(Invariant), 즉 정점 집합 내의 모든 정점에 대한 distTo[]의 정확성과, 정점 집합에서 비정점 집합으로 연결된 모든 간선이 완화되었음에 의해 보장된다.
다익스트라 알고리즘(Dijkstra's Algorithm)의 핵심 원리
다익스트라 알고리즘(Dijkstra's Algorithm)은 가중치가 있는 그래프(Weighted Graph)에서 단일 시작점으로부터 다른 모든 정점까지의 최단 경로를 계산하는 데 사용된다. 알고리즘은 각 정점까지의 최단 거리를 저장하는 `distTo[]` 배열과, 해당 경로의 마지막 간선을 저장하는 `edgeTo[]` 배열을 사용하여 최단 경로 트리(Shortest-Paths Tree, SPT)를 구축한다. 핵심은 간선 완화(Edge Relaxation) 연산으로, 이를 통해 최단 경로를 점진적으로 찾아나간다. 알고리즘은 음수 가중치를 가진 간선이 없는 경우에만 정확하게 동작한다.
최단 경로 트리(Shortest-Paths Tree, SPT)의 구조
알고리즘의 결과는 단순히 거리의 모음이 아닌, 시작 정점을 루트로 하는 최단 경로 트리(Shortest-Paths Tree, SPT)이다. 이 트리는 시작 정점으로부터 도달 가능한 모든 정점까지의 최단 경로를 인코딩한다. `edgeTo[]` 배열은 트리 구조를 나타내며, 각 정점에서 시작 정점까지의 경로를 추적할 수 있게 한다. SPT는 GPS, 네트워크 라우팅, 게임 AI 등 다양한 분야에서 활용되며, 효율적인 경로 탐색을 가능하게 한다.
알고리즘의 정확성을 보장하는 불변성(Invariant)
다익스트라 알고리즘(Dijkstra's Algorithm)의 정확성은 두 가지 핵심 불변성(Invariant)에 의해 보장된다. 첫째, Settled Invariant는 정점 집합에 있는 모든 정점에 대해 `distTo[]` 값이 실제 최단 경로 거리를 나타낸다는 것을 보장한다. 둘째, Frontier Invariant는 정점 집합에서 비정점 집합으로 연결되는 모든 간선이 완화되었음을 보장한다. 이러한 불변성은 알고리즘이 최적의 경로를 찾도록 돕는 핵심 요소이다.
우선순위 큐(Priority Queue)의 역할
다익스트라 알고리즘(Dijkstra's Algorithm)에서 우선순위 큐(Priority Queue)는 가장 작은 `distTo` 값을 가진 정점을 선택하는 데 사용된다. 알고리즘은 우선순위 큐에서 정점을 추출하고, 해당 정점의 모든 연결된 간선을 완화한다. 이 과정은 모든 정점이 처리될 때까지 반복되며, 우선순위 큐는 알고리즘의 효율성을 결정하는 중요한 요소이다. 우선순위 큐(Priority Queue)를 통해, 알고리즘은 가장 짧은 경로를 가진 정점을 먼저 탐색하여 최적의 해를 찾아낸다.
