다익스트라 알고리즘은 1개의 시작점에서 시작해 모든 정점으로 가는 최단 경로를 구하는 알고리즘입니다. 정점의 수가 V, 간선의 수가 E일 때 다익스트라 알고리즘은 기본적으로 O(V * V)의 시간이 걸리지만, 최적화를 하면 O(V log V + E)의 시간이 걸리게 됩니다.

다익스트라 알고리즘은 아래 작업을 계속 반복하며 최단 거리를 찾습니다.

  1. 아직 방문하지 않은 정점 중 거리가 가장 짧은 정점을 방문한다. 거리가 같은 정점이 여러 개일 경우 어떤 것을 방문해도 상관없다.
  2. 해당 정점과 연결되었고 아직 방문하지 않은 정점의 거리를 갱신한다.

만약 음수 간선이 존재할 경우 다익스트라는 최단 경로를 찾을 수 없는데 왜냐하면 항상 현재 방문하지 않은 간선 중 가중치가 가장 작은 간선만 선택하므로 만약 더 멀리 돌아가는 경로 중간에 매우 큰 음의 가중치를 가진 간선이 있다고 해도 그 간선까지 가는 경로가 최단 거리에 포함되지 않는다면 그 간선을 탐색하지 않게 되므로 최적해를 구할 수 없습니다.

쉽게 그림으로 설명하자면 아래 그림에서 정점 1에서 시작해 3번 정점으로 가는 최단 거리는 정점 1-2-3을 방문 하는 것입니다. 간선 2-3이 -10이므로 3까지 가는 최단 거리는 1이 되어야 하고, 이 거리를 답으로 구해야 하지만 다익스트라는 항상 현재 정점과 연결된 간선 중 가중치가 가장 작은 간선부터 보기 때문에 최단 거리를 1-3으로 구하게 됩니다.

실제로 어떻게 동작하는지 BOJ 1753번 문제의 예제 입력을 이용하여 보겠습니다. 가장 먼저 시작점의 거리를 0, 다른 정점의 거리를 무한으로 초기화하고 시작합니다. 이 예제에서 시작점은 1번 정점입니다.

현재 선택한 정점인 1번 정점과 연결된 간선들을 확인합니다. 간선 (1, 3)과 (1, 2)가 있습니다. 이 간선의 정보를 이용하여 최단 거리를 계산하면 됩니다. 정점 x까지 가는 최단 거리를 dist[x] 라고 하고 정점 u와 v를 잇는 간선의 거리를 w(u, v)라 하겠습니다. 만약 dist[v]가 dist[u] + w(u, v)보다 작다면, 즉 지금까지 알고 있는 정점 v로 가는 거리보다 현재 정점을 거쳐 가는 것이 더 짧은 거리라면 최단 거리를 갱신해주면 됩니다.

현재 선택한 정점인 1번 정점과 연결된 간선들을 확인합니다. 간선 (1, 3)과 (1, 2)가 있습니다. 이 간선의 정보를 이용하여 최단 거리를 계산하면 됩니다. 정점 x까지 가는 최단 거리를 dist[x] 라고 하고 정점 u와 v를 잇는 간선의 거리를 w(u, v)라 하겠습니다. 만약 dist[v]가 dist[u] + w(u, v)보다 작다면, 즉 지금까지 알고 있는 정점 v로 가는 거리보다 현재 정점을 거쳐 가는 것이 더 짧은 거리라면 최단 거리를 갱신해주면 됩니다.

1번 정점은 방문 했으니 다른 방문하지 않은 다른 정점 중 거리가 가장 짧은 정점을 선택합니다. 2번 정점이 선택되고 다시 2번 정점과 연결된 간선들을 통해 거리를 갱신합니다. 3번 정점은 정점을 통해 가는 것보다 짧으므로 갱신되지 않으며 4번 정점만 갱신됩니다.

같은 작업을 계속 반복합니다. 이번에는 방문하지 않은 정점 중 거리가 제일 짧은 3번 정점에서 시작하지만 4번 정점은 현재 거리가 더 짧으므로 갱신되지 않습니다.

이 작업을 계속 하다보면 결국 아래와 같이 모든 정점과 방문하고 모든 간선을 확인하게 되고 위 예제에 대한 답은 아래와 같이 나오게 됩니다.

BOJ 1753번 문제를 해결하는 다익스트라 알고리즘을 C++로 구현한 코드는 아래와 같습니다.

#include <cstdio>
#include <vector>
#include <utility>
#define INF 987654321
#define P pair<int, int >
using namespace std;

vector<int> dijkstra(int V, int K, vector<P> *edges) {
	//거리 배열을 INF 값으로 초기화
	vector<int> dist(V + 1, INF);
	//방문 배열을 모두 false 초기화
	vector<bool> visit(V + 1, false);
	//시작 정점의 거리는 0으로 초기화 한다
	dist[K] = 0;
	//모든 정점을 찾기 위하여 사용하지 않는 정점 0의 거리를 INF + 1로 바꾼다.
	dist[0] = INF + 1;
	while (true) {
		int cur = 0;
		//모든 정점을 확인하며 거리가 방문하지 않은 가장 짧은 정점을 선택한다
		for (int i = 1; i <= V; i++)
			if (!visit[i] && dist[i] < dist[cur])
				cur = i;
		//어떠한 정점도 선택할 수 없었다면 반복문을 종료한다
		if (cur == 0) break;
		//선택한 정점을 방문했다 표시한다
		visit[cur] = true;
		//현재 정점과 연결된 간선들을 순회한다
		for (int i = 0; i < edges[cur].size(); i++) {
			int next = edges[cur][i].first;
			int next_cost = edges[cur][i].second;
			// 연결된 정점까지 가는 데 현재 정점을 거쳐 가는 것이 더 짧다면 거리를 갱신한다
			if (dist[next] > next_cost + dist[cur])
				dist[next] = next_cost + dist[cur];
		}
	}
	return dist;
}

int main() {
	int V, E, K;
	vector<P> edges[20001];
	scanf("%d%d%d", &V, &E, &K);
	for (int i = 0; i < E; i++) {
		int u, v, w;
		scanf("%d%d%d", &u, &v, &w);
		edges[u].push_back(P(v, w));
	}
	vector<int> result = dijkstra(V, K, edges);
	for (int i = 1; i <= V; i++) {
		if (result[i] == INF) printf("INF\n");
		else printf("%d\n", result[i]);
	}
}

하지만 이 코드로 1753번 문제를 해결할 수는 없습니다. 모든 정점을 선택해야 하므로 while 문은 V번 반복되는데 매번 선택하는 과정이 O(V) 시간이 걸리므로 총 O(V * V + E) 시간이 걸립니다. 그런데 문제에서 V 제한이 20,000이므로 최악의 경우 O(4억)이므로 문제 제한 시간을 훌쩍 넘겨 시간 초과가 발생합니다. 모든 정점을 선택해야 하는 것은 줄일 수 없으나 거리가 가장 짧은 정점을 선택하는 과정은 조금 더 짧게 바꿀 수 있습니다. 항상 거리가 가장 짧은 정점을 선택해야 한다는 것을 생각해보면 이 부분은 최소 힙으로 바꿀 수 있습니다. 최소 힙은 구현에 따라 다르지만, 피보나치 힙을 기준으로 삭제 연산이 O(log N) 그 외의 모든 연산이 O(1)의 시간이 걸리므로 다익스트라 알고리즘에 적용한다면 알고리즘의 시간 복잡도는 O(V log V + E)로 줄어들게 됩니다. 마침 C++에는 힙을 구현한 라이브러리가 있습니다. 바로 <queue>의 std::priority_queue입니다. 아래 코드는 std::priority_queue를 이용하여 구현한 다익스트라 알고리즘입니다.

#include <cstdio>
#include <vector>
#include <queue>
#include <utility>
#include <functional>
#define INF 987654321
#define P pair<int, int >
using namespace std;

vector<int> dijkstra(int V, int K, vector<P> *edge) {
	//방문 배열을 모두 false 초기화
	vector<bool> visit(V + 1, false);
	//거리 배열을 INF 값으로 초기화
	vector<int> dist(V + 1, INF);
	//최소 힙을 선언한다. 힙은 간선(거리, 도착 정점)을 저장한다.
	priority_queue<P, vector<P>, greater<P>> pq;
	//힙에 시작 정점을 삽입한다.
	pq.push(P(0, K));
	//시작 정점의 거리는 0으로 초기화 한다
	dist[K] = 0;
	while (!pq.empty()) {
		int cur;
		//방문하지 않은 가장 짧은 정점을 선택한다
		do {
			int cur = pq.top().second;
			pq.pop();
		} while (!pq.empty() && visit[cur]);
		//선택한 정점을 방문했다 표시한다
		visit[cur] = true;
		//현재 정점과 연결된 간선들을 순회한다
		for (int i = 0; i < edge[cur].size(); i++) {
			int next = edge[cur][i].first;
			int next_cost = edge[cur][i].second;
			// 연결된 정점까지 가는 데 현재 정점을 거쳐 가는 것이 더 짧다면 거리를 갱신한다
			if (dist[next] > dist[cur] + next_cost) {
				dist[next] = dist[cur] + next_cost;
				pq.push(P(dist[next], next));
			}
		}
	}
	return dist;
}

int main() {
	int V, E, K;
	scanf("%d%d%d", &V, &E, &K);
	vector<P> edge[20001];
	for (int i = 0; i < E; i++) {
		int u, v, w;
		scanf("%d%d%d", &u, &v, &w);
		edge[u].push_back(P(v, w));
	}
	vector<int> result = dijkstra(V, K, edge);
	for (int i = 1; i < result.size(); i++) {
		if (result[i] == INF) printf("INF\n");
		else printf("%d\n", result[i]);
	}
}