실전 알고리즘 0x1D강 - 다익스트라 알고리즘

다익스트라 알고리즘(1950년대)

[ 알고리즘 설명 ]

- 하나의 시작점으로부터 다른 모든 정점까지의 최단 거리를 구하는 알고리즘

- 플로이드 알고리즘은 음수인 사이클만 아니면 음수인 간선이 있어도 작동하지만 다익스트라 알고리즘은 음수인 간선이 있으면 작동하지 않는다. ( 벨만포드 알고리즘을 사용하면 해결된다. )

- 길찾기 알고리즘으로 A*알고리즘이 있다. (내비게이션에서의 길 찾기처럼 100% 정확한 최단거리를 내지 않아도 되고 정점의 개수가 너무 많아 현실적으로 다익스트라 알고리즘을 사용할 수 없을 때 쓰는 근사 알고리즘이다)

 

[ 구현 ]

- 새로운 정점을 추가할 때 모든 정점에서 추가된 정점까지 거리를 확인하면 O(VE)가 되고 미리 거리를 계산해두고 거기서 최솟값을 찾는다면 O(V^2+E)가 되어 효율이 좋아진다.

- 더 빠르게 동작할 수 있는 구현방법이 있다. ( O(E logE)인 알고리즘 존재 )

- 시간 복잡도가 O(V^2+E)인 코드 

vector<pair<int, int>> adj[20005];
const int INF = 0x3f3f3f3f;
bool fix[20005];
int d[20005];
int V = 10;
void dijkstra_native(int st) {
	fill(d, d + V + 1, INF); // 최단 거리 테이블 초기화
	d[st] = 0;
	while (true) {
		int idx = -1;
		for (int i = 1; i <= V; i++) {
			if (fix[i]) continue;
			if (idx == -1) idx = i;
			else if (d[i] < d[idx]) idx = i;
		}
		if (idx == -1 || d[idx] == INF) // 더 이상 선택할 정점이 없으면
			break;
		fix[idx] = 1; // 정점 idx 고정
		for (auto nxt : adj[idx])
			d[nxt.Y] = min(d[nxt.Y], d[idx] + nxt.X);
	}
}

- 우선순위 큐를 이용한 다익스트라 알고리즘 ( 시간 복잡도는 O(E logE) = O(E logV)이다 ) 

1. 우선순위 큐에 (0,시작점)을 추가

2. 우선순위 큐에서 거리가 가장 작은 원소를 선택, 해당 거리가 최단 거리 테이블에 있는 값과 다를 경우 넘어감

3. 원소가 가리키는 정점을 v라고 할 때, v와 이웃한 정점들에 대해 최단 거리 테이블 값보다 v를 거쳐가는 것이 더 작은 값을 가질 경우 최단 거리 테이블의 값을 갱신하고 우선순위 큐에 (거리, 이웃한 정점의 번호)를 추가

4. 우선순위 큐가 빌 때 까지 2, 3번 과정을 반복

 

백준 1753번 : https://www.acmicpc.net/problem/1753

 

[ 경로 복원 방법 ]

- 최단 거리 테이블이 갱신될 때, 어디를 거쳐가면 되는지를 pre 테이블에 저장하면 된다. (우선순위 큐에서 원소를 꺼낼 때, 거리가 최단 거리 테이블과 같으면 우선순위 큐의 정점을 그 정점과 연결된 정점의 인덱스에 우선순위 큐의 정점 값을 저장한다. 

- 백준 11779번 : https://www.acmicpc.net/problem/11779