다익스트라(Dijkstra) 최단 경로 알고리즘
다익스트라 알고리즘은 가중치 그래프에서 하나의 정점부터 다른 모든 정점 까지의 최단 경로를 찾는 알고리즘으로, 현재까지 발견된 경로들 중 가장 짧은 거리의 정점부터 차례로 선택하여 그 정점과 인접한 노드들의 최단 거리를 갱신해 나가는 방식으로 동작한다. 다익스트라 알고리즘에서의 최단 거리는 지나온 경로의 가중치를 더해서 거리를 비교하기 때문에 음수 가중치 그래프는 이 알고리즘을 적용할 수 없다.
다익스트라 알고리즘을 활용하기 위해서는 최단 경로를 저장할 '최단 거리 배열(distance array)'과 각 시점에서 가장 가까운 정점을 알아내기 위한 '최소 힙 기반 우선순위 큐(min-heap priority queue)'를 활용한다. 알고리즘은 시작 정점에서부터 인접 노드들 까지의 경로 비용을 탐색하며 최단 경로를 발견한 경우 거리 배열에 해당 정점까지의 거리 비용을 기록하고 우선순위 큐에 추가한다. 우선순위 큐는 최소힙을 기준으로 하여 항상 가장 가까운 정점이 맨 앞에 위치하고 있다. 우선순위큐에서 노드를 하나씩 꺼내 그 정점을 기준으로 다시 인접 노드들 까지의 거리를 확인하며, 더 짧은 경로가 발견되면 거리 배열을 갱신하고 큐에 새로 삽입힌다. 우선순위 큐가 비어있다면 더이상 탐색할 정점이 없다는 의미이므로 알고리즘을 종료하고 거리 배열에는 시작 정점부터 각 정점까지의 최단 경로가 확정된다.
알고리즘 동작 방식
- 최단 거리 배열 dist[]를 무한대로 초기화하고 시작 정점의 거리를 0으로 지정하여 우선순위 큐에 시작 정점을 추가한다.
- 우선순위 큐에서 맨 앞 노드(가장 가까운 정점)을 꺼낸다. 이 정점의 비용이 최단 거리 배열에 저장된 값 보다 크다면 건너뛴다.
- 우선순위 큐에 꺼낸 정점의 인접 정점들을 탐색한다. ‘현재 거리 + 인접 정점까지의 거리’가 최단 거리 배열에 저장되어있는 값보다 작다면 최단 경로 갱신으로 배열에 ‘현재 거리 + 인접 정점까지의 거리’를 기록하고 갱신된 인접 정점을 우선순위 큐에 추가한다.
- 우선순위 큐가 빌때까지 2~3번 과정을 반복한다. 알고리즘이 종료되면 최단 거리 배열 dist[]에는 시작 정점으로부터 각 정점까지의 최단 거리가 저장되어있다.
// 그래프 G는 인접 리스트 형태로 주어진다고 가정
// G[u] = (v, w) 리스트 → u에서 v로 가는 간선, 가중치 w
// dist[] : 최단 거리 저장 배열
// pq : (거리, 정점) 형태의 우선순위 큐 (최소 힙)
function Dijkstra(G, start):
// 1. 초기화
for each vertex v in G:
dist[v] ← ∞
dist[start] ← 0
create priority_queue pq
pq.push( (0, start) )
// 2. 반복
while pq is not empty:
(curDist, u) ← pq.top()
pq.pop()
// 이미 더 짧은 경로가 발견된 경우 스킵
if curDist > dist[u]:
continue
// 3. 인접 노드 탐색
for each (v, weight) in G[u]:
newDist ← curDist + weight
// 더 짧은 경로 발견 시 갱신
if newDist < dist[v]:
dist[v] ← newDist
pq.push( (newDist, v) )
return dist
최단 거리의 경로 추적
위 방법으로는 한 정점으로부터의 각 정점까지의 최단 거리를 알 수 있다. 그러면 어떤 노드를 거쳐서 그 정점에 도착했는지에 대한 경로 정보는 알 수 있을까? 이전 노드 배열(prev array)를 사용하여 최단 거리 배열에 누적거리 최소값을 갱신할 때마다 각 정점에 도달하기 직전의 정점을 저장해주면 된다. 그러면 prev[4]의 값은 정점 4번에 최단 거리로 도달하기 위해 거쳐온 이전 정점의 값이 저장된다. 알고리즘이 종료되어있을때 4번 정점까지의 최단 경로를 추적하고 싶다면 prev[4]부터의 값을 역추적하면 이동 경로를 알아낼 수 있다.
C++ 코드
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
using namespace std;
/* 정점 구조체 */
struct Vertex {
int data; // 정점
vector<pair<int, int>> adjacencyList; // 인접 리스트 {목적 정점 index, 가중치}
};
/* 그래프 구조체 */
struct Graph {
vector<Vertex> vertexs;
explicit Graph(int n) : vertexs(n) {}
// 정점 설정
void SetNode(int i, int d)
{
vertexs[i].data = d;
}
// 간선 추가
void AddDirectedEdge(int from, int to, int weight)
{
vertexs[from].adjacencyList.push_back({ to, weight });
}
// 그래프 출력
void PrintGraphNodeAndEdge() const
{
cout << "그래프를 출력합니다." << endl;
for (int i = 1; i < vertexs.size(); ++i) {
cout << vertexs[i].data << " :";
for (auto& e : vertexs[i].adjacencyList)
cout << "(" << e.first << "," << e.second << ") ";
cout << endl;
}
}
// [다익스트라(dijkstra) 최단 경로 알고리즘]
/* 최단 경로 배열 dist[], 경로 추적용 이전 정점 배열 prev[], 최소힙 우선순위 큐 pq
1. 최단 거리 배열 dist[]를 무한대로 초기화하고 시작 정점의 거리를 0으로 지정하여 우선순위 큐에 시작 정점을 추가한다.
2. 우선순위 큐에서 맨 앞 노드(가장 가까운 정점)을 꺼낸다. 이 정점의 비용이 최단 거리 배열에 저장된 값 보다 크다면 건너뛴다.
3. 우선순위 큐에 꺼낸 정점의 인접 정점들을 탐색한다. ‘현재 거리 + 인접 정점까지의 거리’가 최단 거리 배열에 저장되어있는 값보다 작다면 최단 경로 갱신으로 배열에 ‘현재 거리 + 인접 정점까지의 거리’를 기록하고 갱신된 인접 정점을 우선순위 큐에 추가한다.
4. 우선순위 큐가 빌때까지 2~3번 과정을 반복한다. 알고리즘이 종료되면 최단 거리 배열 dist[]에는 시작 정점으로부터 각 정점까지의 최단 거리가 저장되어있다.
*/
void Dijkstra(int start) {
const int INF = 1e9;
// 1. start init
vector<int> dist(vertexs.size(), INF); // 최단 거리 배열
vector<int> prev(vertexs.size(), -1); // 이전 정점 배열 (경로 추적용)
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; // 최소힙 기반 우선순위큐 (거리, 정점 번호)
dist[start] = 0;
pq.push({ 0, start});
// 2~3. 최단 경로 갱신
while (!pq.empty()) {
// 현재 시점에서 가장 가까운 정점 cur V
auto curV = pq.top(); pq.pop();
int vertexIndex = curV.second; // 정점 번호
int curDist = curV.first; // 정점까지의 누적 거리
// (2) 꺼낸 정점이 이미 최단 거리 갱신된 정점이라면 건너뜀
if (curDist > dist[vertexIndex]) continue;
// (3) 인접 정점 탐색
for (auto& edge : vertexs[vertexIndex].adjacencyList) {
int nextVIndex = edge.first;
int weight = edge.second;
// 최단 거리 갱신
// '현재정점까지의 거리 + 인접노드까지의 거리' < '최단 거리 배열에 저장된 값' 이면 갱신
if (dist[vertexIndex] + weight < dist[nextVIndex])
{
dist[nextVIndex] = dist[vertexIndex] + weight; // 최단 거리 갱신
prev[nextVIndex] = vertexIndex; // 이전 정점 기록
pq.push({ dist[nextVIndex], nextVIndex}); // 우선순위큐에 추가
}
}
}
// 최단 거리
cout << "\n=== 최단 거리 출력 ===" << endl;
for (int i = 1; i < vertexs.size(); ++i)
{
if (dist[i] == INF) cout << vertexs[i].data << ": INF\n";
else cout << vertexs[i].data << ": " << dist[i] << "\n";
}
// 최단 경로
cout << "\n=== 최단 경로 출력 ===" << endl;
for (int goal = 1; goal < vertexs.size(); ++goal)
{
cout << vertexs[goal].data << " : ";
if (dist[goal] == INF)
{
cout << "경로 없음\n";
continue;
}
// 이전 정점 배열 역추적
stack<int> path;
for (int v = goal; v != -1; v = prev[v])
path.push(v);
while (!path.empty())
{
cout << vertexs[path.top()].data << "(" << dist[path.top()] << ") -> ";
path.pop();
}
cout << endl;
}
}
};
int main() {
Graph graph(6); // 0~5
// 정점
graph.SetNode(1, 1);
graph.SetNode(2, 2);
graph.SetNode(3, 3);
graph.SetNode(4, 4);
graph.SetNode(5, 5);
// 간선
graph.AddDirectedEdge(1, 2, 8);
graph.AddDirectedEdge(1, 3, 3);
graph.AddDirectedEdge(2, 4, 4);
graph.AddDirectedEdge(2, 5, 15);
graph.AddDirectedEdge(3, 4, 13);
graph.AddDirectedEdge(4, 5, 2);
graph.PrintGraphNodeAndEdge();
// 최단 경로 알고리즘
graph.Dijkstra(1);
return 0;
}
'CS > 자료구조, 알고리즘' 카테고리의 다른 글
| [알고리즘] A* 최단 경로 알고리즘 (0) | 2025.10.31 |
|---|---|
| [알고리즘] 위상 정렬 알고리즘(Topological Sort Algorithm) - 멀티 스레드를 활용한 Task 스케줄링 병렬 처리 (0) | 2025.10.31 |
| [자료구조] 그래프(Graph) (0) | 2025.10.15 |
| [알고리즘] 슬라이딩 윈도우(Sliding Window) 알고리즘과 단조 큐(Monotonic Queue) (0) | 2025.09.19 |
| [알고리즘] 'N의 연속된 자연수의 합 찾기'와 투 포인터(Two Pointers) 알고리즘 (0) | 2025.09.18 |