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

다익스트라 알고리즘(Dijkstra Algorithm)은 저명한 컴퓨터 과학자인 에르허츠 다익스트라(Edsger Wybe Dijkstra)가 고안한 간선(Edge)에 가중치가 주어진 그래프에서 정점(Vertex)간의 최단 경로를 찾는 알고리즘입니다.

 

최단 경로 알고리즘에는 여러 종류가 있지만, 그중에서도 다익스트라 알고리즘은 하나의 정점에 대한 모든 정점의 최단 경로를 찾는데 사용됩니다. 단, 가중치가 음수인 간선이 있으면 사용할 수 없습니다.

 

처음에 에르허츠 다익스트라가 고안한 다익스트라 알고리즘의 시간복잡도는 정점의 갯수를 $V$, 간선의 갯수를 $E$라고 했을 때, $O(V^2)$였으나, 우선순위 큐(Priority Queue)등을 접목해 그 비용이 $O(E+V log V)$까지 개선되었습니다.

 

다음은 다익스트라 알고리즘을 사용하는 최단 경로 문제입니다. 

https://www.acmicpc.net/problem/1753

1753번: 최단경로

다음은 C++로 구현한 위의 문제의 해답입니다. 정점의 갯수가 최대 20,000개 이므로, 인접 행렬(Adjacency matrix)를 통해 간선을 int edge[20000][20000]같은 방식으로 저장할 수 없습니다. 배열의 사이즈가 너무 크기 때문이죠.

 

이럴때 인접 리스트(Adjacency list)를 사용하면 이러한 문제를 풀 수 있습니다. 인접 행렬은 간선A와 간선 B가 연결되어 있지 않더라도 edge[A][B]와 같이 메모리를 차지하게 되는 반면, 인접 리스트는 존재하는 간선에 대해서만 데이터가 저장되어 메모리를 절약할 수 있습니다.

#include <iostream>
#include <climits>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
struct compare { //pair의 second를 기준으로 min heap 구현
	bool operator()(pair<int, int> a, pair<int, int> b) {
		if (a.second == b.second) return a.first > b.first;
		else return a.second > b.second;
	}
};

int v, e, k; //정점 갯수, 간선 갯수, 시작 정점 번호
int d[20001]; //최단거리 저장 배열
priority_queue<pair<int, int>, vector<pair<int, int>>, compare> pq; 
vector<pair<int, int>> edge[20001]; //간선을 저장하기 위한 인접 리스트

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	for (int i = 0; i < 20001; i++) d[i] = INT_MAX; //거리 배열 int 최댓값으로 초기화

	cin >> v >> e;
	cin >> k;

	for (int i = 0; i < e; i++) { //입력
		int u, v, w; //현재 정점, 목적지 정점, 가중치
		cin >> u >> v >> w;
		edge[u].push_back({ v,w });
	}

	d[k] = 0; //자기 자신의 거리는 0임
	pq.push({ k,0 });

	while (!pq.empty()) {
		int current = pq.top().first; //현재 인덱스
		int weight = pq.top().second; //현재까지의 최소거리
		pq.pop();
		if (weight > d[current]) continue; //만약 지금 꺼낸 것보다 더 짧은 경로가 있으면 무시

		for (int i = 0; i < edge[current].size(); i++) { //모든 노드 탐색
			int dest = edge[current][i].first; //목표 노드 인덱스
			int dest_weight = edge[current][i].second + weight; //목표 노드까지의 최소거리
			if (d[dest] > dest_weight) { //기존의 최소거리와 비교
				d[dest] = dest_weight; //값 갱신
				pq.push({dest,d[dest]}); 
			}
		}
	}

	for (int i = 1; i <= v; i++) { //출력
		if (d[i] == INT_MAX) cout << "INF" << "\n";
		else cout << d[i] << "\n";
	}

	return 0;
}