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

 가중치가 있는 그래프에서 최단 경로를 찾는 알고리즘에는 대표적으로 다익스트라, 벨만-포드, 플로이드-워셜이 있다. 그 중 다익스트라에 대해서 정리하는 글이다.

 

 다익스트라 알고리즘은 우선순위 큐를 이용할 경우 O(E + VlogV)로 알려져 있다. 여기서 E는 간선의 개수이고, V는 정점의 개수이다. 이 알고리즘은 무향, 유향 상관없이 적용 가능하지만, 음의 가중치가 있으면 사용할 수 없다. 다익스트라 알고리즘은 하나의 시작 정점에서 다른 정점들과의 최단 시간을 알아낼 때, 즉 1 : N일 때 사용할 수 있다.

 

 다익스트라 알고리즘을 C++로 구현한 코드는 다음과 같다.

#define INF 1000000000

int v;
vector<vector<pair<int, int>>> edges;
vector<int> dijkstra(int start)
{
	vector<int> dist(v + 1, INF);
	priority_queue<pair<int, int>> pq;

	dist[start] = 0;
	pq.push(make_pair(0, start));

	while (!pq.empty())
	{
		int cost = -pq.top().first;
		int present = pq.top().second;
		pq.pop();

		for (int i = 0; i < edges[present].size(); i++)
		{
			int next = edges[present][i].first;
			int nextDist = cost + edges[present][i].second;

			if (dist[next] > nextDist)
			{
				dist[next] = nextDist;
				pq.push(make_pair(-nextDist, next));
			}
		}
	}

	return dist;
}

 이는 가장 기본적인 형태이고, 약간의 코드를 추가하면 더 빠르게 수행할 수 있다. 18번째 줄에 다음 코드를 삽입하면 된다.

if (dist[present] < cost)
{
	continue;
}

 이는 이미 dist[present] 에 있는 값이 더 작아 비교할 필요가 없기 때문에 가능하다. 

 

다익스트라는 start로부터 다른 모든 정점들과의 최단 시간을 구할 수 있지만, 만약 start가 아닌 다른 하나의 정점과의 최단 시간만을 구하고 싶다면 역시 18번째 줄에 다음을 추가함으로써 시간을 줄일 수 있다.

if (present == end)
{
	break;
}

 

 만약 최단 시간이 걸리는 경로를 역추적하고 싶다면 24번째 줄 if문 안에서 next의 이전 노드를 저장하는 prev 배열을 만들어 저장해놓고, 알고리즘이 끝난 후 prev[end] 부터 start에 도달할 때까지 추적하면 된다.

 

 

 

 

 

참고

- 알고리즘 문제 해결 전략(구종만 저)

- https://ko.wikipedia.org/wiki/%EB%8D%B0%EC%9D%B4%ED%81%AC%EC%8A%A4%ED%8A%B8%EB%9D%BC_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98