다익스트라(Dijkstra)의 최단 경로 알고리즘은 가장 유명한 그래프 알고리즘 중 하나입니다. 다익스트라 알고리즘은 단일 시작점 최단 경로 알고리즘으로, 시작 정점 s에서부터 다른 정점들까지의 최단 거리를 계산합니다.
너비 우선 탐색에서는 큐에 정점의 번호를 넣었지만, 다익스트라 알고리즘에서는 우선순위 큐에 정점의 번호 와 함께 지금까지 찾아낸 해당 정점까지의 최단 거리 를 쌍으로 넣습니다. 우선순위 큐는 정점까지의 최단 거리를 기준으로 정점을 배열함으로써, 아직 방문하지 않은 정점 중 시작점으로부터의 거리가 가장 가까운 점을 찾는 과정을 간단하게 해줍니다.
우선순위 큐를 사용한다는 점을 제외하면 다익스트라 알고리즘의 구조는 너비 우선 탐색과 비슷합니다. 각 정점까지의 최단 거리를 저장하는 배열 dist[]를 유지하며, 정점을 방문할 때마다 인접한 정점을 모두 검사합니다. 간선 (u, v)를 검사했는데 v가 만약 아직 방문하지 않은 정점이라고 합시다. 그러면 u까지의 최단 거리에 (u, v)의 가중치를 더해 v까지의 경로의 길이를 찾습니다. 이것이 지금까지 우리가 찾은 최단 거리라면 dist[v]를 갱신하고 (dist[v], v)를 큐에 넣는 것입니다.
// 정점의 개수
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[]를 갱신하고 우선순위 큐에 넣는다.
if (dist[there] > nextDist) {
dist[there] = nextDist;
pq.push(make_pair(-nextDist, there));
}
}
}
return dist;
}
pair를 비교할 때는 첫 번째 원소를 먼저 비교하므로 정점까지의 거리를 첫 번째 원소로, 정점의 번호를 두 번째 원소로 하였습니다. priority_queue는 기본적으로 가장 큰 원소가 위로 가도록 큐를 구성하기 때문에, 거리의 부호를 바꿔서 거리가 작은 정점부터 꺼내지도록 하는 것에 주목합시다. 우선순위 큐의 원소들은 작은 것부터 꺼내지므로, 어떤 원소 (cost, u)를 꺼냈는데 dist[u]가 cost보다 작다면 이 원소는 중복으로 들어간 원소임을 알 수 있지요. 따라서 무시하고 다음 원소를 꺼냅니다.
시간 복잡도
하나는 각 정점마다 인접한 간선들을 모두 검사하는 작업이고, 다른 하나는 우선순위 큐에 원소를 넣고 삭제하는 작업입니다. 각 정점은 정확히 한 번씩 방문되고, 따라서 모든 간선은 한 번씩 검사된다는 사실을 떠올리면 간선들을 검사하는 데는 전체 O(|E|)의 시간이 걸립니다.
우선순위 큐가 가장 커지는 최악의 시나리오는 그래프의 모든 간선이 검사될 때마다 dist[]가 갱신되고 우선순위 큐에 정점의 번호가 추가되는 것입니다. 이때 추가는 각 간선마다 최대 한 번 일어나기 때문에, 우선순위 큐에 추가되는 원소의 수는 최대 O(|E|)의 시간이 걸리고, O(|E|)개의 원소에 대해 이 작업을 하려면 전체 시간 복잡도는 O(|E||log|E|)가 됨을 알 수 있습니다.
이 두 작업에 걸리는 시간을 더하면 O(|E||log|E|)가 됩니다만, 대개의 경우 그래프에서 간선의 개수 |E|는 |V|^2보다 작기 때문에 O(log|E|)=O(log|V|)라고 볼 수 있습니다. 따라서 시간 복잡도는 O(|E||log|V|)가 됩니다.
우선순위 큐를 사용하지 않는 다익스트라 구현
정점의 수가 적거나 간선의 수가 매우 많은 경우에는 아예 우선순위 큐를 사용하지 않고 구현하는 방식이 더욱 빠른 경우가 있습니다. 이 방식에서는 다음에 방문할 정점을 별도의 큐에 보관하는 대신 매번 반복문을 이용해 방문하지 않은 정점 중 dist[]가 가장 작은 값을 찾습니다. 각 정점을 방문했는지 여부를 나타내는 별도의 배열 visited[]를 유지하는 것을 볼 수 있습니다. 이 경우 다익스트라 알고리즘의 시간 복잡도는 O(|V|^2+|E|)가 됩니다.
vector<int> dijkstra2(int src) {
vector<int> dist(V, INF);
// 각 정점을 방문했는지 여부를 저장한다.
vector<bool> visited(V, false);
dist[src] = 0; visited[src] = true;
while (true) {
// 아직 방문하지 않은 정점 중 가장 가까운 정점을 찾는다.
int closest = INF, here;
for (int i = 0; i < V; ++i) {
if (dist[i] < closest && !visited[i]) {
here = i;
closest = dist[i];
}
}
if (closest == INF) break;
// 가장 가까운 정점을 방문한다.
visited[here] = true;
for (int i = 0; i < adj[here].size(); ++i) {
int there = adj[here][i].first;
if (visited[there]) continue;
int nextDist = dist[here] + adj[here][i].second;
dist[there] = min(dist[there], nextDist);
}
}
return dist;
}