[알고리즘] 다익스트라(Dijkstra)의 최단경로 알고리즘

다익스트라 알고리즘은 단일 시작점 최단 경로 알고리즘으로, 시작 정점 s에서 다른 정점들까지의 최단거리를 계산하는 알고리즘이다.

 

BFS 알고리즘의 경우

가중치가 있는 그래프에선 너비우선 탐색을 그대로 적용하는데에는 어려움이 있다.

위의 예시처럼 BFS로 시작점 S에서 C까지의 최단 경로를 구하고자한다면,

S->A->C->이런 순서로 탐색이 진행되어 S->C: 12의 거리가 된다.

그러나 실제 S에서 C로 가는 최단 거리 경로는 S->A->B->C로 A, B를 거쳐 도착하는 경로이다.

즉, 더 늦게 발견한 정점이더라도 더 먼저 방문할 수 있어야 하는데 BFS에서는 그게 되지 않아 실제 최단 경로를 찾는데에 문제가 생기는 것이다.

 

다익스트라 알고리즘

다익스트라 알고리즘은 큐를 사용하는 BFS와 달리 우선순위 큐를 사용함으로써 위와 같은 문제를 해결한다. 큐에 정점의 번호만을 넣던 BFS와 달리 다익스트라 알고리즘에서는 정점의 번호와 최단거리를 쌍으로 넣는다. 우선순위 큐는 정점까지의 최단거리를 기준으로 정점을 배열하여 아직 방문하지 않은 정점 중 시작점으로 부터의 거리가 가장 가까운점을 찾는 과정을 좀더 간단하게 해준다.

 

우선순위 큐르 사용한다는 점을 제외하고는 BFS와 매우 비슷하다.

각 정점까지의 최단거리를 모두 저장하는 배열 dist[]를 유지한다. 정점 방문시마다 인접한 정점을 모두 검사하며 간선 (u, v)를 검사했는데 v가 아직 방문되지 않은 정점인 경우 u까지의 거리에 간선(u, v)의 가중치를 더해 V까지의 경로의 길이를 구한다.

 

이때 중요한 것은 각 정점까지의 최단 경로가 갱신될 수 있다는 것이다.

3에서 우선순위큐에 이미 들어있는 (C, 12)를 처리하는 방식은 2가지가 있다.

1. 우선순위큐 내에서 (C, 12)를 찾아 (C, 9)로 바꾼다.

2. (C, 12)를 그대로 두고 (C, 9)를 추가한 뒤, 나중에 큐에서 (C, 12)가 꺼내지면 무시한다.

대체로는 2의 방법을 사용한다.

2의 방법의 경우 정점 번호u와 최단거리 cost의 쌍을 큐에서 뽑은 후, dist[u]와 cost를 비교하여 dist[u] < cost라면 이 쌍은 무시하면된다.

 

C++에서의 구현

int V;	//정점의 개수

vector<pair<int, int>> adj[MAX_V];	//그래프의 인접리스트. (연결된 정점 번호, 간선가중치)

vector<int> dijkstra(int src) {
	vector<int> dist(V, INF);
	dist[src] = 0;
    
	priority_queue<pair<int, int>> pq;
	pq.push(make_pair(0, src));

	while (!pq.empty()) {
		int cost = -pq.top().first;
		int here = pq.top().second;
        
		pq.pop();
		// 지금 꺼낸것보다 더 짧은 경로를 알고있다면 경우 무시
		if (dist[here] < cost) continue;

		// 인접한 정점들을 모두 검사
		for (int i=0; i<adj[here].size(); ++i) {
			int there = adj[here][i].first;
			int nextDist = cost + adj[here][i].second;

			// 더 짧은 경로를 발견하면 dist[]를 갱신하고 우선순위큐에 push
			if (dist[there] > nextDist) {
				dist[there] = nextDist;
				pq.emplace(-nextDist, there);
			}
		}
	}
    
    return dist;
}

STL의 priority_queue는 시본적으로 가장 큰 원소가 위로 가도록 큐를 구성하기 때문에 거리의 부호를 바꿔 거리가 작은 정점부터 꺼내지도록 해야한다.

 

 

출처: 알고리즘 문제해결 전략(구종만)