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

최단 거리, 최소 비용 을 구할 때 사용하는 알고리즘이다.
시작 노드가 주어졌을 때, 최소 비용을 갖는 경로를 찾는데 사용된다.

도착 노드가 있을 때도 사용하지만, 도착 노드가 없을 때도 다른 모든 정점들에 대해서도 각각의 최단거리를 찾을 수 있는 알고리즘이다.

BFS도 최단거리를 구할 때 좋은 알고리즘인데,,
가중치가 있는 경우에는 사용할 수 없다.

이외에도, 벨만-포드 알고리즘, 플로이드-와샬 알고리즘 등을 통해서 최단 거리를 구할 수 있다.

구현

기본적인 알고리즘은 아래와 같다.

1. 노드 a 방문
2. a와 인접한 노드들 중, 가장 가중치가 작은 노드 b 방문
3. a를 거쳐 b로 가는 값 < b의 값으로 이미 저장된 값 -> b의 값 갱신

사용할 용어 정리~!
cost : 최소 비용을 저장해놓을 배열
pq : 우선순위 큐

위 알고리즘에서, 이미 저장된 값을 저장해두기 위해서 cost라는 노드의 개수 사이즈의 일차원 배열이 필요하다.

Priority_Queue(우선순위 큐)를 이용해서 푼다.
우선순위 큐 안에 노드의 인덱스와 해당 노드의 비용을 담는다.
우선순위 큐는 비용이 작은 순대로 정렬된다.

저장된 최소비용보다 우선순위 큐에서 나온 비용이 크다면 연산하지 않고 무시하면 된다.

C++ 우선순위 큐를 이용한 다익스트라 코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

struct compare {
	bool operator() (const pair<int, int>& a, const pair<int, int>& b) const {
		return a.second > b.second;
	}
};

priority_queue<pair<int, int>, vector<pair<int, int>>, compare> pq;
vector<vector<pair<int, int>>> vec;
int cost[1001];
int start, dest;

void Dijkstra()
{
	pq.push(make_pair(start, 0));
	cost[start] = 0;

	while (!pq.empty()) {
		int cur = pq.top().first;
		int cst = pq.top().second;
		pq.pop();
		if (cst > cost[cur]) continue;

		for (auto& s : vec[cur]) {
			int next = s.first;
			int nextCost = cost[cur] + s.second;
			if (cost[next] > nextCost) {
				cost[next] = nextCost;
				pq.push(make_pair(next, nextCost));
			}
		}
	}
}

int main()
{
	int n, m;
	cin >> n;
	cin >> m;
	for (int i = 0; i <= n; i++) {
		vec.emplace_back(vector<pair<int, int>>());
		cost[i] = 987654321;
	}

	int s, e, c;
	for (int i = 0; i < m; i++) {
		cin >> s >> e >> c;
		vec[s].emplace_back(make_pair(e, c));
	}

	cin >> start >> dest;

	Dijkstra();

	cout << cost[dest] << endl;
}

시간복잡도

노드의 수 V, 간선의 수 E 일 때,
O(ElogV)

관련 문제

백준 골드5 1916 : 최소비용 구하기
위 문제를 풀고 정리한 글 -> 링크
백준 골드5 17936 : 백도어
위 문제를 풀고 정리한 글 -> 링크

---

참고

https://code-lab1.tistory.com/29

https://ansohxxn.github.io/algorithm%20lesson%202/chapter4-5/

https://velog.io/@717lumos/알고리즘-다익스트라Dijkstra-알고리즘