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

[목차]

1. 1. 다익스트라 알고리즘이란?
2. 알고리즘
   1. 알고리즘 원리
   2. 구현 
      1. O(n²)
      2. O(ElogE)
      3. 알고리즘 분석
3. 의의

 

다익스트라는 일종의 그리디 이다. 왜? 매 순간 다음 정점을 선택할 때 가중치가 최소인 정점을 선택하기 때문이다.

하지만 그리디의 특성상 부분 최적해가 전체의 최적해를 보장해야 위의 선택이 합리적이라고 할 수 있다.

그렇다면 매 순간 최소 가중치를 가진 정점을 선택하면 항상 최소가 보장될까?

직관

 

이를 귀류법으로 증명해보자.

반례

 

 

[원시적인 다익스트라 알고리즘]

#include<iostream>
#include<vector>
#include<algorithm>
#define F first
#define S second

using namespace std;
typedef pair<int, int> PII;

int V, E, st, en;
int d[10001];
bool fix[10001];
vector<PII> g[10001];
const int INF = 0x3f3f3f3f;

void dijkstra(int start) {
	d[start] = 0;
	while (true) {
		int idx = -1;
		//d[V]의 최소 찾기
		for (int i = 1; i <= V; i++) {
			if (fix[i]) continue;	//고정되어 있으면 pass
			if (idx == -1) idx = i;	//초기화
			else if (d[i] < d[idx]) idx = i;	//작으면 갱신 -> 최소찾기
		}
		//더 이상 갈 수 있는 정점이 있는지 체크
		if (idx == -1 || d[idx] == INF) break;	//모두 확정지었거나 간선이 연결이 되어있지 않으면 종료
		fix[idx] = true;
		//d[idx]를 기준으로 최솟값 갱신해놓기
		for (auto nxt : g[idx]) d[nxt.S] = min(d[nxt.S], d[idx] + nxt.F);
	}
}

int main(void) {
	cin >> V >> E >> st >> en;
	while (E--) {
		int u, v, w;
		cin >> u >> v >> w;
		g[u].push_back({w, v});
	}
	
	fill(d, d + V + 1, INF);
	dijkstra(st);
	cout << d[en];

	return 0;
}

 

모든 간선 가중치가 양수일때, 모든 정점쌍에 대한 최단 경로값을 구하려면 프림 알고리즘을 써도 되지만, 각 정점에대해 다익스트라 알고리즘을 써서 구하면 프림보다 빠르게 O(n^2 log n)으로 구할 수있는게 맞을 까요?

•  
  다익스트라를 V번 쓰는 풀이는 O(VElgE)입니다.
  
  간선 개수 E가 작다(=V와 비슷하다) -> 다익스트라 V번이 더 빠름
  
  간선 개수 E가 많다(=V^2와 비슷하다) -> 플로이드 알고리즘이 더 빠름
  
  으로 생각하시면 됩니다.

 

주의 사항: d[]배열 INF로 초기화할 때 단순히 최대 입력보다 약간 큰 수로 초기화하면 안된다.