[알고리즘] 다익스트라

다익스트라 알고리즘이란?

다익스트라는 그래프에서 한 정점에서 다른 정점까지의 최단 경로를 구하는 알고리즘이다.

 

최단 경로 구하는 과정

1. 출발점으로부터의 최단거리를 저장할 배열 d[v]를 만들고, 출발 노드에는 0을, 출발점을 제외한 다른 노드들에는 매우 큰 값 INF를 채워 넣는다.
2. A로부터 갈 수 있는 임의의 노드 B에 대해, d[A] + P[A][B](가중치)와 d[B]의 값을 비교한다.
3. d[A] + P[A][B] < d[B] 라면, d[B] =  d[A] + P[A][B]로 갱신시킨다.
4. A의 모든 이웃 노드 B에 대해 이 작업을 수행한다.
5. A의 방문 상태를 TRUE로 바꾼다. 
6. 방문하지 않은 모든 노드들 중, 출발점으로부터의 거리가 제일 짧은 노드를 다시 A로 지정한다.
7. 도착 노드의 방문 상태가 TRUE가 되거나, 혹은 더 이상 미방문 상태의 노드를 선택할 수 없을 때까지, 3~7의 과정을 반복한다.

이 작업을 마친 뒤, 도착 노드에 저장된 값이 바로 A로부터의 최단 거리이다. 만약 이 값이 INF라면, 중간에 길이 끊긴 것임을 의미한다.

 

다익스트라 알고리즘 예시

출발점 1번 노드의 거리는 0으로, 방문 상태는 TRUE로 설정하고 나머지 노드는 모두 거리 INF, 방문 상태는 FALSE로 초기화한다.

1번 노드에서 갈 수 있는 2번, 3번 6번 노드에서 모두 거리가 INF로 저장되어 있으므로, 각 노드까지의 비용으로 갱신해준다. 

1번 노드로부터 거리가 가장 짧은 2번 노드를 방문한다.

2번 노드에서 갈 수 있는 3번, 4번 노드에서 3번 노드는 d[2] + 10 > d[3] 이므로 원래의 값을 유지하고, 4번 노드는 거리가 INF이니 d[2] + 15 = 22로 갱신해준다.

1번 노드로부터 거리가 가장 짧은 3번 노드를 방문한다.

3번 노드에서 방문할 수 있는 4번, 6번 노드에서 4번 노드는 d[3] + 11 < d[4] 이므로 d[3] + 11 = 20으로 갱신해주고, 6번 노드도 d[3] + 2 < d[6] 이므로 d[3] + 2 = 11로 갱신해준다.

1번 노드로부터 가장 거리가 짧은 6번 노드를 방문한다.

6번 노드에서 방문할 수 있는 5번 노드에서 거리가 INF이니 d[6] + 9 = 20으로 갱신해준다. 이때 4번과 5번 모두 거리가 20 이므로 아무 노드나 먼저 방문해도 된다. 나는 5번 노드를 먼저 방문해보겠다.

마지막으로 4번 노드를 방문하면 최단 경로를 구할 수 있다.

다익스트라는 (N - 1)번 탐색 x (최단 거리 정점 찾기(N번 순차탐색)) = O(N^2) 의 시간복잡도를 갖는다.

 

다익스트라 알고리즘 구현 - C++

위에서 설명한 것을 코드로 구현해보자.

#include<iostream>
#include<vector>
#define INF 1e9 

using namespace std;

int V, E, start; //노드 개수, 간선 개수, 시작 노드 번호

vector<pair<int, int> > graph[100001]; // 그래프
bool visited[100001] = { false, }; // 방문 상태
int d[100001]; // 최단 거리

int getSmallestNode() // 방문하지 않은 노드 중에서, 가장 거리가 짧은 노드의 번호를 반환
{
	int min_val = INF;
	int index = 0; 

	for (int i = 1; i <= V; i++){
		if (d[i] < min_val && !visited[i]){
			min_val = d[i]; // 거리가 가장 작은 값
			index = i; //노드 번호
		}
	}

	return index;
}

void dijkstra(int start)
{
	d[start] = 0;
	visited[start] = true;

	for (int i = 0; i < graph[start].size(); i++){ 
		int node = graph[start][i].first;
		d[node] = graph[start][i].second; // 시작 노드와 연결된 노드의 최단 거리 초기값 세팅
	}

	for (int i = 0; i < V - 1; i++){
		int now = getSmallestNode();
		visited[now] = true;

		for (int j = 0; j<graph[now].size(); j++){
			int cost = d[now] + graph[now][j].second;

			if (cost < d[graph[now][j].first]){	// (현재 노드 -> 다음 노드) vs (시작 노드 -> 다음 노드)
				d[graph[now][j].first] = cost;
			}
		}
	}
}

int main(){
	cin >> V >> E >> start;
	
	for (int i = 0; i < E; i++){
		int from, to, cost;
		cin >> from >> to >> cost;  // from 노드에서 to 노드로 가는 비용 cost
		graph[from].push_back({ to, cost });
	}

	fill_n(d, 100001, INF);

	dijkstra(start);

	for (int i = 1; i <= V; i++){	//모든 노드의 최단 거리 출력
		if (d[i] == INF){
			cout << "INFINITY" << '\n';
		}
		else{
			cout << d[i] << '\n';
		}
	}

	return 0;
}

 

우선순위 큐로 구현하기

 우선순위 큐로 구현하게 되면 O(E * logN) (E = 간선의 수, N = 정점의 수) 의 시간복잡도를 갖는다.

#include<iostream>
#include<vector>
#include<queue>
#define INF 1e9 

using namespace std;

int V, E, start; //노드 개수, 간선 개수, 시작 노드 번호

vector<pair<int, int> > graph[100001]; // 그래프
int d[100001]; // 최단 거리

void dijkstra(int start){
	priority_queue<pair<int, int>>pq;
	
	pq.push({ 0, start });	//시작 노드까지의 최단거리는 0
	d[start] = 0;
	
	while (!pq.empty()) {
		int dist = -pq.top().first;
		int now = pq.top().second;
		pq.pop();

		if (d[now] < dist)
			continue;

		for (int i = 0; i < graph[now].size(); i++) {
			int cost = dist + graph[now][i].second;

			if (cost < d[graph[now][i].first]) {
				d[graph[now][i].first] = cost;
				pq.push({ -cost, graph[now][i].first }); // -로 들어가야 큰 순으로 정렬
			}
		}
	}
}

int main(){
	cin >> V >> E >> start;
	
	for (int i = 0; i < E; i++){
		int from, to, cost;
		cin >> from >> to >> cost;  // from 노드에서 to 노드로 가는 비용 cost
		graph[from].push_back({ to, cost });
	}

	fill_n(d, 100001, INF);

	dijkstra(start);

	for (int i = 1; i <= V; i++){	//모든 노드의 최단 거리 출력
		if (d[i] == INF){
			cout << "INFINITY" << '\n';
		}
		else{
			cout << d[i] << '\n';
		}
	}

	return 0;
}