[Algorithm] 다익스트라(Dijkstra) - 최단거리, 최소비용 경로 구하기

다익스트라(Dijkstra) ❓

• 그래프 한 지점에서 갈 수 있는 모든 지점에 대해서 최단 거리를 구하는 알고리즘이다.
• 출발지부터 목적지까지의 경로들에 대해 가중치를 부여하여 최소의 비용을 도출하는 방식이다

이전 글에서 'DFS로 최소항공권 비용 구하기' 문제를 소개한 적이 있다. DFS로 최소항공권 비용을 구할 때에는, 예를 들면 A와 B라는 지점을 특정하여(또는 지정하여) 갈 수 있는 모든 경로별로 소요되는 비용의 배열을 만들었다. 그 다음, 그 배열의 최솟값(최소비용)과 경로를 도출해내었다.

사실, 그 방법으로 최소비용을 구해도 무방하긴 하며, 최소경로를 구하는 좋은 방법이다. 하지만, 다익스트라(Dijkstra) 대비해서는 아래와 같은 비효율이 있을 것이라고 생각한다.

• DFS에서는 출발지에서 갈 수 있는 경로를 특정하게 된다. 재귀방식으로 구현 시, 멈춰줄 지점으로 Return 지점을 설정하게 되므로..
  ✔ 다익스트라의 경우, 출발지에서 갈 수 있는 모든 지점에 대해서 최소값을 구현하게 된다.

• DFS의 경우, 모든 경로의 가중치가 1로 가정되어 있기 때문에, 굳이 방문하지 않아도 되는 지점에 대해서도 배열에 저장해두었다가, 최소값을 구해야하는 불편함이 있다.
  ✔ 다익스트라의 경우, 최소값을 갱신하므로 추가적으로 배열에 저장하여 최소값을 구할 필요가 없다.

다익스트라에 대한 소스코드를 리뷰하시기 전에 일전에 올린 DFS로 최소항공권 비용구하기 문제를 먼저 리뷰해주시고 오시면 더 좋을 것 같다! 👏
(링크 👉 https://velog.io/@hw8129/Algorithm-DFS%EB%A1%9C-%EC%B5%9C%EC%86%8C-%ED%95%AD%EA%B3%B5%EA%B6%8C-%EB%B9%84%EC%9A%A9-%EA%B5%AC%ED%95%98%EA%B8%B0)

위 그래프의 0번 Index를 출발점으로 하여, 각 Index별 최소 비용을 구하게 되며, 갱신되는 비용은 아래 result 배열에 저장된다. 또한, 이미 지나온 경유지(via)는 다시 지나지 않도록 해야하기 때문에, used 배열을 사용하여 가지치기를 해준다.
(※used 배열 초기 값 0으로 세팅)

result 배열의 경우, min값 갱신을 위해 각 지점마다 9999로 세팅하였다. min값 또는 max값 갱신할 때, 조금 오버해서 초기 값을 세팅하는데, 이렇게 세팅해줘야 안전한 경우가 많다
예를 들면, max값의 경우 배열의 초기값을 세팅하거나, -1을 세팅하기도 한다 (0의 경우, 상황에 따라 위험하다). 물론, 정해진 것은 없고, 예상되는 입력값에 따라 갱신을 위한 초기값을 설정해주는 것이 뻔하지만 안전한 원칙이다.

위 표는 제시된 그래프를 하드코딩한 값이며, 입력된 순으로 탐색을 시작하게 된다.
시작지 0에서서는 1,2,3으로 갈 수 있으며, 각 비용(가중치)는 다음과 같이 갱신된다.

result에는 각 경유지까지 도착하는 비용을 갱신하였으며, priority queue에는 maxheap 구조(최대값이 우선순위)로 저장하여, result배열에 최소값이 갱신되도록 하였다. 단, 여기서는 구조체(Node)를 사용하므로, 연산자 오버로딩(Bool operator)을 사용하여 maxheap 구조를 만들어주었다.

queue의 다음 값이 차례대로 경유지가 되며, 경유지별로 계속해서 result값 (비용)을 갱신하게 되고, queue 값이 비게 되면, 0에서 갈 수 있는 모든 경로에 대해 최소 가중치 값을 구할 수 가 있다.
(만약 최단 거리라면, 모든 가중치를 1로 두고 구하면 된다)

#include <iostream>
#include <vector>
#include <queue> 
using namespace std;
struct Node {   // Node에는 경유지, 가중치(비용)이 저장됨
	int n;
	int price;
}; 

vector<vector<Node>> alist(5);
int used[5] = { 0 };
int result[5] = { 0,9999,9999,9999,9999 }; 
// 비용배열, 갱신을 위해 초기값은 의도적으로 높게 설정
bool operator<(Node v, Node tar) {
	return v.price > tar.price;
}
priority_queue<Node> q;
void init() {
	alist[0].push_back({ 1,25 });
	alist[0].push_back({ 2,50 });
	alist[0].push_back({ 3,10 });
	alist[1].push_back({ 2,3 });
	alist[2].push_back({ 4,1 });
	alist[3].push_back({ 4,18 });
	alist[3].push_back({ 1,5 });
}

int main() {

	init();
	q.push({ 0,0 }); //시작점은 먼저 넣고 시작한다. 

	while (!q.empty()) {

		Node via = q.top();
		q.pop();

		if (used[via.n] == 1) continue; //이미 경유한 지점의 경우 넘어간다.
		used[via.n] = 1;

		for (int i = 0; i < alist[via.n].size(); i++) {
			Node tar = alist[via.n][i]; //목표로 한 지점을 target 변수에 넣어준다.
		
			if (result[tar.n] > via.price + tar.price) {
				result[tar.n] = via.price + tar.price;
				q.push({ tar.n, result[tar.n] });
				// result배열에 최소값을 갱신해주고, queue에 경유지를 넣어준다. 
			}
		}
	}

	return 0;
}