[Algorithm/Graph] 다익스트라 최단 경로 알고리즘(Dijkstra's algorithm)

단일 시작 최단 경로 문제

"주어진 그래프에서 시작 정점과 목적 정점이 주어질 때 시작 정점에서 목적 정점까지 이어지는 최소 비용 경로를 구하는 문제"

 

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

• 음수 가중치가 없는 그래프에서 동작하는 최단 경로 탐색 알고리즘으로 프림의 MST 알고리즘을 약간 변형한 형태이다.
• 프림 알고리즘과 다익스트라 알고리즘의 차이점
  • 프림 알고리즘 : 경계로부터 최소 거리의 정점의 거리 값으로 설정. 모든 정점을 방문해야 종료
  • 다익스트라 알고리즘 : 시작 정점으로부터 각 정점까지의 전체 거리를 사용. 목적 정점이 나타나면 종료

 

다익스트라 알고리즘의 동작

1. 모든 정점의 거리 값을 무한대로 초기화한다. 시작 정점에서 자기 자신까지의 거리는 0이므로 시작 정점의 거리 값은 0으로 설정한다. 그리고 모든 거리 값을 최소 힙 H에 추가한다
2. 최소 힙 H로부터 정점을 하나 꺼낸다. 이 정점을 U라고 하면, 정점 U는 경계에서 가장 가까이 있는 정점이다. 만약 U가 목적 정점이면 최단 경로를 찾은 것이므로 알고리즘을 종료한다
3. U와 인접한 모든 정점 V에 대해, 만약 V의 거리 값이 (U의 거리값 + (U, V)의 에지 가중치)보다 크면 V까지 다다르는 더 짧은 경로를 찾은 것으로 볼 수 있다. 그러므로 V의 거리 값을 (U의 거리값 + (U, V)의 에지 가중치)로 설정한다. 이 과정을 정점 U에 안착했다고 한다.
4. 방문하지 않은 정점이 남아 있다면 2단계로 이동한다
5. 최소 힙 H로부터 꺼낸 정저이 목적 정점이면 알고리즘이 종료한다.

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

template <typename T>
auto dijkstra_shortest_path(const Graph<T>& G, unsigned src, unsigned dst)
{
	// 최소 힙
	priority_queue<Label<T>, vector<Label<T>>, greater<Label<T>>> heap;

	// 모든 정점에서 거리 값을 최대로 설정
	vector<T> distance(G.vertices(), numeric_limits<T>::max());

	set<unsigned> visited;					// 방문한 정점
	vector<unsigned> parent(G.vertices());	// 이동 경로를 기억을 위한 벡터

	heap.emplace(Label<T>{src, 0});
	parent[src] = src;

	while (!heap.empty())
	{
		auto current_vertex = heap.top();
		heap.pop();

		// 목적지 정점에 도착했다면 종료
		if (current_vertex.ID == dst)
		{
			cout << current_vertex.ID << "번 정점(목적 정점)에 도착!" << endl;
			break;
		}

		// 현재 정점을 이전에 방문하지 않았다면
		if (visited.find(current_vertex.ID) == visited.end())
		{
			cout << current_vertex.ID << "번 정점에 안착!" << endl;

			// 현재 정점과 연결된 모든 에지에 대해
			for (auto& e : G.edges(current_vertex.ID))
			{
				auto neighbor = e.dst;
				auto new_distance = current_vertex.distance + e.weight;

				// 인접한 정점의 거리 값이 새로운 경로에 의한 거리 값보다 크면
				// 힙에 추가하고, 거리 값을 업데이트함.
				if (new_distance < distance[neighbor])
				{
					heap.emplace(Label<T>{neighbor, new_distance});

					parent[neighbor] = current_vertex.ID;
					distance[neighbor] = new_distance;
				}
			}

			visited.insert(current_vertex.ID);
		}
	}

	// 백트래킹 방식으로 시작 정점부터 목적 정점까지의 경로 구성
	vector<unsigned> shortest_path;
	auto current_vertex = dst;

	while (current_vertex != src)
	{
		shortest_path.push_back(current_vertex);
		current_vertex = parent[current_vertex];
	}

	shortest_path.push_back(src);
	reverse(shortest_path.begin(), shortest_path.end());

	return shortest_path;
}

 

위 함수는 두 개의 부분으로 나눌 수 있다.

앞부분에서는 시작 정점부터 목적 정점까지의 탐색을 수행한다.

뒷 부분에서는 탐색 결과를 목적 정점에서 시작 정점까지 백트래킹 방식으로 되짚어가면서 최단 경로를 구한다.

 

시간 복잡도

피보나치 최소 힙을 사용하여 구현한 다익스트라 알고리즘의 시간 복잡도는 O(E + VlogV이다)