최단 경로 - 다익스트라 알고리즘(Dijkstra Algorithm)

최단 경로

: 그래프에서 정점 u로부터 정점 v로 가는 경로 중에서 에지들의 가중치 합이 최소가 되는 경로. 혹은 에지의 개수가 가장 적은 경로.

 

 

 

다익스트라 알고리즘 (Dijkstra Algorithm)

: 시작 정점으로부터 다른 모든 정점까지의 최단 경로를 찾을 수 있는 알고리즘.  

 

 

 

 

 

▷ 아이디어

 

: 방문하지 않은 정점 중에서 가장 비용이 적은 에지로 연결된 정점을 방문. 시작 정점으로부터 해당 정점을 경유지로 하여 다른 정점을 방문하는 비용이 더 작다면, 최단 경로값을 갱신.

 

위의 그림에서 distance[u]가 distance[w]값보다 작아서 가장 비용이 적은 에지로 연결된 정점 u가 새롭게 추가되었다면(방문되었다면), 시작 정점 v로부터 해당 정점 u를 거쳐서 다른 정점인 w로 가는 비용을 계산한다. 만약 distance[w]값보다 distance[u] + weight[u][w]값이 더 작다면 distance[w]값이 distance[u] + weight[u][w]값으로 갱신된다.

 

 

 

 

 

 

▷ 알고리즘

 

1. 시작정점을 선택하고, 시작정점을 기준으로 모든 정점까지의 최단경로를 계산

2. 비용이 가장 적은 에지로 연결된 정점을 방문

3. 시작정점으로부터 새롭게 방문한 정점을 거쳐서 다른 정점을 가는 경로를 계산

4. 기존에 저장되어 있던 최단 경로와 3번에서 계산한 값을 비교하여 더 적은 값을 취함

5. 모든 정점이 방문될 때까지 시행.

 

 

 

 

 

 

▷ 프로그램

int start;
vector<pair<int, int>> graph[MAX];
int distance[MAX]; // 매우 큰 값으로 초기화해두어야 함

void dijkstra() {
	priority_queue<pair<int, int>> pq; // 방문할 정점 목록을 저장.
	distance[start] = 0;
	pq.push(make_pair(0, start));

	while (pq.empty() == 0) {
		int current = pq.top().second;
		int cDistance = -pq.top().first; //비용이 적은 에지가 우선적으로 선택되게 만들기 위해.
		pq.pop();

		if (distance[current] < cDistance) continue; // 최단 경로가 아닌 경우 스킵

		for (int i = 0; i < graph[current].size(); i++) {
			int next = graph[current][i].first;
			int nDistance = graph[current][i].second;
			if (nDistance + cDistance < distance[next]) { // 새롭게 구한 거리가 더 적은 비용을 가진다면
				d[next] = nDistance + cDistance; // 최단 경로값 갱신
				pq.push(make_pair(-d[next], next));
			}
		}
	}
}

 

 

 

 

 

 

▷ 시간 복잡도

: 힙 구조를 활용해 다음에 방문할 정점을 선택하기 때문에 O(nlogn)의 시간 복잡도를 가짐.