[알고리즘] 다익스트라 알고리즘 (최단 경로 알고리즘) - 이론편

다익스트라 알고리즘은 가장 유명한 그래프 알고리즘 중 하나입니다.

 

그래프에서 정점끼리의 최단 경로를 찾는 경우가 여러 가지가 있습니다.

1. 하나의 정점에서 다른 하나의 정점까지의 최단 거리 ( Single source and Single destination shortest path )

2. 하나의 정점에서 다른 모든 정점까지의 최단 거리 ( Single source shortest path )

3. 하나의 목적지로 가는 모든 최단 거리 ( Single destination shortest path )

4, 모든 최단 거리 ( All pairs shortest path )

 

다익스트라 알고리즘은 여기서 2번째인 시작 정점 s에서 다른 정점들까지의 최단 거리를 계산합니다.

 

다익스트라 알고리즘은 너비 우선 탐색과 유사한 형태를 가진 알고리즘으로, 너비 우선 탐색처럼 시작점에서 가까운 순서대로 정점을 방문해 갑니다. 물론, 가중치가 있는 그래프에서는 너비 우선 탐색을 그대로 적용할 수 없습니다.

다음 예시를 보겠습니다.

너비 우선 탐색이 최단 거리를 찾지 못하는 그래프의 예

위의 문제를 해결할 때, 너비 우선 탐색을 사용한다고 생각해봅니다. 큐를 사용해서 문제를 해결할 경우 시작점에서부터 가까운 순서로 큐에 넣으며 큐에 비어 있을 때까지 탐색을 합니다.

너비 우선 탐색을 사용할 경우, s에서 각 정점으로 가는 최단 거리

너비 우선 탐색은 각 정점을 발견한 순서대로 방문하기 때문에 a와 c를 방문한 후에야 b를 방문하게 됩니다.

하지만 s에서 c까지 가는 최단 경로는 s-a-b-c 이기 때문에, 최단 거리 순서대로 정점들을 방문하려면 a -> b -> c 순서로 각 정점을 방문해야 합니다.

즉, 더 늦게 발견된 정점이라도 더 먼저 방문할 수 있어야 합니다.

우선 순위 큐를 사용할 경우, s에서 각 정점으로 가는 최단 거리

다익스트라 알고리즘은 큐 대신 우선순위 큐를 사용함으로써 이 문제를 해결합니다.

너비 우선 탐색에서는 큐에 정점의 번호와 함께 지금까지 찾아낸 해당 정점까지의 최단 거리를 쌍으로 넣습니다.

우선 순위큐는 정점까지의 최단 거리를 기준으로 정점을 배열함으로써, 아직 방문하지 않은 정점 중 시작점으로부터 거리가 가장 가까운 점을 찾는 과정을 간단하게 해 줍니다.

다익스트라 알고리즘에서 최단 경로 계산

우선순위 큐를 사용한다는 점을 제외하면 다익스트라 알고리즘의 구조는 너비 우선 탐색과 비슷합니다.

각 정점까지의 최단 거리를 저장하는 배열 dist[]를 유지하며, 정점을 방문할 때마다 인접한 정점을 모두 검사합니다.

간선 (u, v)를 검사했는데, v가 만약 아직 방문하지 않은 정점이라고 합니다.

그러면 u까지의 최단 거리에 (u, v)의 가중치 w(u, v)를 더해 v까지의 경로의 길이를 찾습니다.

이것이 지금까지 우리가 찾은 최단 거리라면 dist[v]를 갱신하고 (dist[v], v)를 큐에 넣는 것입니다.

 

즉 dist[v] = min(dist[v], dist[u] + w(u, v)) 로 수식을 만들 수 있습니다.

 

이때 유의해야 할 점은 각 정점까지의 최단 경로가 갱신될 수 있다는 점입니다.

 

위의 예시에서 보면 시작점을 방문하고 나면 (a, 1)과 (c, 12)가 우선순위 큐에 들어갑니다.

최단 거리 순으로 정점들을 큐에서 꺼내면 c는 큐에 그대로 있고, a와 b가 순서대로 방문되게 됩니다.

문제는 b가 방문될 때, b까지의 최단 경로에 (b, c) 간선을 덧붙이면 s에서 c로 가는 길이 6이 되므로 s->c로 바로 가는 12보다 거리가 짧은 것을 알 수 있습니다.

이때 큐에 남아있는 (c, 12)는 어떻게 해야 할까요?

# 우선순위 큐 내에서 (c, 12)를 찾아내 (c, 6)으로 바꾼다.

# (c, 12)를 그대로 두고 (c, 6)을 추가한 뒤, 나중에 (c, 12)가 꺼내지면 무시한다.

 

실제 두 번째 방법을 많이 사용합니다.

큐에서 정점 번호 u와 최단거리 cost의 쌍을 뽑아낸 후, dist[u]와 cost를 비교합니다.

만약 dist[u] < cost라면 u까지 오는 cost보다 짧은 경로가 이미 발견됐다는 의미이므로 (u, cost)쌍은 무시하면 됩니다.

 

실제 구현 소스코드 및 예제는 다익스트라 알고리즘을 사용하는 문제를 통해 학습하도록 하겠습니다.

 

※ 참조

알고리즘 문제 해결 전략

 

※ 예제 문제

1. 파티 ( 백준 1238번 문제 ) : https://www.acmicpc.net/problem/1238

1238번: 파티

2. 알고스팟 ( 백준 1261문제 ) : https://www.acmicpc.net/problem/1261

1261번: 알고스팟