06 - 3. 다익스트라 최단 경로 알고리즘

 

그래프에서 단일 시작 최단 경로 문제는 구글 지도 또는 네비게이션 등에서 경로를 탐색할 때 사용된다.

다익스트라 알고리즘은 음수 가중치가 없는 그래프에서 동작하는 최단 경로 탐색 알고리즘으로 프림의 MST 알고리즘을 약간 변경한 형태이다.

 

 

두 알고리즘의 차이점은 다음과 같다.

 

- 프림 알고리즘은 경계로부터 최소 거리를 정점의 거리 값으로 설정하지만, 다익스트라 알고리즘은 시작 정점으로부터 각 정점까지의 전체 거리를 사용한다.

 

- 다익스트라 알고리즘은 목적 정점이 나타나면 종료하지만, 프림 알고리즘은 모든 정점을 방문해야 종료된다.

 

 

---

 

다익스트라 알고리즘 과정

 

1. 시작 정점을 제외한 모든 정점의 거리 값을 무한대로 초기화하고 모든 거리 값을 최소 힙 H에 추가한다.

 

2. 최소 힙 H로부터 꺼낸 하나의 정점을 U라고 하면, 정점 U는 시작 정점에서 가장 가까운 정점이다. 

만약 U가 목적 정점이면 최단 경로를 찾은 것이므로 알고리즘을 종료한다.

 

3. U와 인접한 모든 정점 V에 대해, 만약 V의 거리 값이 (U의 거리 값 + (U, V) 엣지 가중치)보다 크면 V까지 다다르는 더 짧은 경로를 찾은 것으로 볼 수 있으므로 V의 거리 값을 (U의 거리 값 + (U, V) 엣지 가중치)로 업데이트 해준다.

이러한 과정을 정점 U에 안착했다고 한다.

 

4. 방문하지 않은 정점이 남아있다면 2단계로 이동한다.

 

 

전체 코드 및 실행 결과

 

#include <iostream>
#include <vector>
#include <set>
#include <limits>
#include <queue>
#include <algorithm>

#include "graph_and_edge.h"
#include "Label.h"

using namespace std;

/*
* 아래 함수는 두개의 부분으로 나눌 수 있다.
* 1. 시작 정점부터 목적 정점까지 탐색을 수행한다.
* 2. 탐색 결과를 목적 정점에서 시작 정점까지 백트래킹 방식으로 되짚어가며 최단 경로를 구한다.
*/
template <typename T>
vector<unsigned> 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());	// 이동 경로 기억을 위한 벡터

	// 시작 정점: 자기 자신으로의 거리 0으로 설정
	heap.emplace(Label<T>{src, 0});
	parent[src] = src;

	while (!heap.empty()) {
		Label<T> curr_vertex = heap.top();
		heap.pop();

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

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

			// 현재 정점과 연결된 모든 엣지에 대해
			for (Edge<T>& e : G.edges(curr_vertex.ID)) {
				unsigned neighbor = e.dst;
				unsigned new_distance = curr_vertex.distance + e.weight;

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

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

			visited.insert(curr_vertex.ID);
		}
	}

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

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

	std::reverse(shortest_path.begin(), shortest_path.end());
	
	return shortest_path;
}

int main() {
	using T = unsigned;

	Graph<T> G = create_reference_graph2<T>();

	cout << "[입력 그래프]" << endl;
	cout << G << endl;

	vector<unsigned> shortest_path = dijkstra_shortest_path(G, 1, 6);

	cout << "\n[1번과 6번 정점 사이의 최단 경로]" << endl;
	for (unsigned v : shortest_path) cout << v << " ";
	cout << endl;
}