[알고리즘] 다익스트라 Dijkstra

다익스트라 알고리즘

음의 가중치가 없는 그래프의 한 정점(vertex)에서 모든 정점까지의 최단 거리를 각각 구하는 알고리즘

 

다익스트라 알고리즘의 초기 시간 복잡도는 O(v^2)의 시간복잡도를 가졌다. 이후 우선순위 큐등을 이용한 개선된 알고리즘이 나오며 O( (V+E)logV )의 시간복잡도를 가지게 되었다.

이유는 각 노드마다 미방문 노드 중 출발점으로부터 현재까지 계산된 최단 거리를 가지는 노드를 찾는데 O( V log V)의 [모든 노드 (O(V))에 대해 힙에서 최소값을 추출 (O(log V))] 시간이 필요하고, 각 노드마다 이웃한 노드의 최단 거리를 갱신할 때 O (E log V)의 [각 노드마다 모든 이웃을 확인하는 것은 모든 edge를 확인하는 것과 같고 O(E), 매번 힙에서 최단 거리를 갱신 O(log V)해야 하기 때문] 시간이 필요하기 때문이다.

V: 정점의 개수, E: 한 정점의 주변 노드

 

 

간선들 중 음수가 있으면 다익스트라 알고리즘은 사용할 수 없다. 음의 가중치를 가지는 간선이 있으며, 가중치 합이 음인 사이클이 존재하지 않는 경우는 벨만-포드 알고리즘을 사용 할 수 있다.

그래프 내에 가중치 합이 음인 사이클이 존재한다면 무한히 음의 사이클을 도는 경우 경로 합이 음수 무한대로 발산하기 때문에 그래프 내의 최단 경로는 구성할 수 없다.

 

 

다익스트라 알고리즘: 하나의 노드로부터 최단 경로를 구한다.

플로이드-워셜 알고리즘: 가능한 모든 노드쌍들에 대한 최단거리를 구한다.

 

 + 다익스트라 알고리즘을 확장시킨 알고리즘: A* 알고리즘

 

 

동작 방식 

len[cur][next]는 cur과 next 사이의 거리

1. 출발점으로부터의 최단거리를 저장할 배열 dist[v]를 선언하고 출발 노드에는 0을 (자기 자신까지의 거리는 0, 당연!) 나머지 노드들에는 매우 큰 값 INF를 채워 넣는다. 
2. 현재 노드를 나타내는 변수 int cur에 출발 노드의 번호를 저장한다.
3. cur로부터 갈 수 있는 임의의 노드 next에 대해, dist[cur] + len[cur][next]와 dist[next]의 값을 비교한다. (INF와 비교할 경우 무조건 작은 값)
4. 만약 dist[cur] + len[cur][next]의 값이 더 작다면, dist[next]를 이 값으로 갱신 시킨다.
5. cur의 모든 이웃 노드 next에 대해 위의 작업을 수행한다.
6. 5번 작업을 마치면 cur의 상태를 '방문 완료'로 바꾼다. 이후 더이상 cur은 사용하지 않는다.
7. '미방문' 상태인 모든 노드들 중, 출발점으로부터의 거리가 제일 짧은 노드 하나를 골라서 그 노드를 cur에 저장한다.
8. 도착(목표) 노드가 '방문 완료'가 되거나, 더 이상 미방문 상태의 노드가 없을 경을 때까지 3~7의 과정을 반복한다.

이 작업을 마친 뒤, 도착 노드에 저장된 값이 cur부터 도착 노드 까지의 최단거리이다. 만약 이 값이 INF라면 경로가 존재하지 않다는 것을 의미한다.

 

 

문제

백준 1753번 '최단 경로'

 

 

 

 

 

위의 동작 방식에 따라 코드로 구현해보자.

 

입력은 아래와 같이 받았다.

 

1. 출발점으로부터의 최단거리를 저장할 배열 dist[v]를 선언하고 출발 노드에는 0을 (자기 자신까지의 거리는 0, 당연!) 나머지 노드들에는 매우 큰 값 INF를 채워 넣는다. 

vertex는 간선의 개수. INF는 매우 큰 값

 

2. 현재 노드를 나타내는 변수 int cur에 출발 노드의 번호를 저장한다. 

예제 입력에 따르면 출발 노드는 1이다.

 

3 ~ 7

15) 오름차순 정렬 우선순위 큐 선언

16-17) 출발 노드를 0으로 초기화 (자기 자신과의 거리 = 0) 한 후, queue에 (거리, 노드)를 push

25) cur로부터 갈 수 있는 임의의 노드 next에 대해, dist[cur] + len[cur][next]와 dist[next]의 값을 비교한다.

 -2차원 벡터 vec의 vec[cur]를 탐색하므로, cur에서 접근할 수 있는 노드와 그 가중치를 확인할 수 있다.

 -if (dist[next] > len + nLen)

26) 만약 dist[cur] + len[cur][next]의 값이 더 작다면, dist[next]를 이 값으로 갱신 시킨다.

27) 도착(목표) 노드가 '방문 완료'가 되거나, 더 이상 미방문 상태의 노드가 없을 경을 때까지 3~7의 과정을 반복한다.

 

전체 코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

#define INF 1e8

using namespace std;

int vertex, edge, k;
vector<pair<int, int>> vec[20001];
int dist[20001];

void dijkstra(int idx) {
	priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq;
	dist[idx] = 0;
	pq.push(make_pair(0, idx));
	while (!pq.empty()) {
		int cur = pq.top().second;
		int len = pq.top().first;
		pq.pop();
		for (int i = 0; i < vec[cur].size(); i++) {
			int next = vec[cur][i].first;  // cur과 연결된 다음 방문할 노드
			int nLen = vec[cur][i].second;  // cur부터 next 까지의 거리
			if (dist[next] > len + nLen) {
				dist[next] = len + nLen;
				pq.push(make_pair(dist[next], next));
			}
		}
	}
}


int main() {
	cin >> vertex >> edge >> k;
	for (int i = 0; i < edge; i++) {
		int u, v, w;
		cin >> u >> v >> w;  // u에서 v로 가는 가중치 w인 간선 존재
		vec[u].push_back(make_pair(v, w));
	}
	fill(dist, dist + (vertex + 1), INF);
	dijkstra(k);
	for (int i = 1; i <= vertex; i++) {
		if (dist[i] == INF)
			printf("INF\n");
		else
			printf("%d\n", dist[i]);
	}
}

cout을 사용하면 시간초과가 난다. printf()로 변경해줬다..