[알고리즘] 다익스트라

다익스트라(Dijsktra)

그래프에서 한 정점(노드)에서 다른 정점까지의 최단 경로를 구하는 알고리즘이다.

• 가중치가 양수인 그래프에서 사용할 수 있다.

위와 같이 정점까지의 거리를 갱신하며 탐색한다.

문제를 통해 더 자세히 살펴보자.

---

백준 1753 최단경로

1753 최단경로

코드

#include<bits/stdc++.h> 
using namespace std;
const int INF = 987654321;
int V,E,K,u,v,w;
vector<pair<int,int>> adj[20001];
int dist[20001];
priority_queue<pair<int,int>, vector<pair<int,int>> , greater<pair<int,int>>> pq;
int main(){
	cin>>V>>E>>K;
	fill(dist,dist+20001, INF);
	for(int i=0; i<E; i++){
		cin>>u>>v>>w;
		adj[u].push_back({w,v});
	}
	pq.push({0,K});
	dist[K]=0;
	while(pq.size()){
		int here = pq.top().second;
		int here_dist = pq.top().first;
		pq.pop();
		if(dist[here] != here_dist) continue;
		for(pair<int,int> there : adj[here]){
			int _dist = there.first;
			int _there = there.second;
			if(dist[_there]>dist[here]+_dist){
				dist[_there]=dist[here]+_dist;
				pq.push({dist[_there],_there});
			}
		}
	}
	for(int i=1; i<=V; i++){
		if(dist[i]==INF) cout<<"INF\n";
		else cout<<dist[i]<<"\n";
	}
	return 0;
}

1. 정점까지의 거리 초기화

fill(dist,dist+20001, INF);

최소값을 구하는 문제이므로, 초기값을 INF로 설정해 놓는다.

2. 시작정점

pq.push({0,K});
dist[K]=0;

시작정점인 K부터 거리 0으로 시작한다.

3. 탐색

while(pq.size()){
	int here = pq.top().second;
	int here_dist = pq.top().first;
	pq.pop();
	if(dist[here] != here_dist) continue;
	for(pair<int,int> there : adj[here]){
		int _dist = there.first;
		int _there = there.second;
		if(dist[_there]>dist[here]+_dist){
			dist[_there]=dist[here]+_dist;
			pq.push({dist[_there],_there});
		}
	}
}

정점을 방문한 후, 연결된 정점을 순회하며 방문하며, 정점까지의 최솟값을 갱신해준다.

위와 같은 순서로 탐색을 진행한다.

4. 출력

for(int i=1; i<=V; i++){
	if(dist[i]==INF) cout<<"INF\n";
	else cout<<dist[i]<<"\n";
}

정점까지의 최단거리를 출력한다.

왜 우선순위 큐를 사용하는가?

결론적으로 말해서 최소거리 값 갱신 횟수의 증가 때문이다. 우선순위 큐를 쓰지 않고 일반 큐를 써도 결과에는 차이가 없지만, 갱신 횟수에서 차이가 난다.

예를 들어 아래와 같은 그래프가 있다고 가정해보자.

1. 일반 큐

A->B->C->E->B->D->E 순서로 탐색한다.
시간복잡도 O(V^2) 를 가진다.

2. 우선순위 큐

A->C->B->B->D->E 순서로 탐색한다.
시간복잡도 O(ElogV) 를 가진다.

일반 큐와 다르게 가중치가 낮은 간선을 먼저 탐색함으로써 불필요한 탐색을 줄여준다.

일반 큐에서는 B간선을 먼저 탐색하고, 이후에 B가 새로운 값으로 갱신되면서 B와 연관된 간선들을 다시 갱신해줬어야 했는데, 우선순위 큐를 사용하면 C간선 이후에 B간선을 탐색하므로, 불필요하게 다시 B간선을 갱신하는 탐색을 줄여준다.

if(dist[here] != here_dist) continue;

3. 탐색 코드를 잘 살펴보면, 중간에 다음과 같은 코드가 있다.

if(dist[here] != here_dist) continue;

이 코드는 어떤 역할을 할까?

코드를 해석해보면, pq에 있는 거리와 dist에 갱신된 거리를 비교해서, 일치하지않으면 무시(continue)한다. 즉, pq에 있는 거리가 최신 갱신된 거리가 아니면 고려할 필요가 없으니, 무시하는 것이다.

1753 최단경로 문제는 위 코드가 없어도 잘 작동하지만, 잘 만들어진 다익스트라 문제는 위 코드가 있어야 통과할 수 있다. 그러니 위 코드의 형태를 기본 형식으로 생각해두고 숙지해두자.