다익스트라

한 개의 특정 정점에서 다른 모든 정점까지의 최소 cost를 구하는데 쓰이는 알고리즘

 

---

[Dijkstra vs Floydwarshall]

 

둘 다 정점에서 정점까지의 최단거리를 구하는 알고리즘임 ㅇㅇ

근데 다른 점이 있음

이게 Floydwarshall이랑 다른점이다

 

Dijkstra는 최종답이 1차원 배열임 but Floydwarshall은 최종답이 2차원 배열임

 

because Floydwarshall은 특정 노드에 대한 다른 모든 노드까지의 최단거리만 구하는게 아니라

모든 노드에 대한 모든 노드까지의 최단거리를 구해주는 알고리즘이기 때문

 

쉽게 말하면 다익스트라는 1:N 플로이드워셜은 N:N 이다 ㅇㅇ

 

따라서 특정 노드에 대한 다른 모든 노드까지의 최단거리를 구한 배열이 총 N개있으니

2차원 배열로 답이 나오는 것이다

 

이게 다익스트라랑 플로이드워셜의 차이점이다

 

---

1. 특정 노드를 우선순위 큐에 넣는다는 것

	while (!pq.empty()) {
		int cost_so_far = pq.top().first;
		int curnode = pq.top().second;
		pq.pop();

		// 기존에 계산된 curnode까지의 최소거리보다 크다면 스킵
		if (cost_so_far > ans[curnode]) continue;

		for (int i = 0; i < graph[curnode].size(); i++) {
			int next = graph[curnode][i].first;
			int cost = graph[curnode][i].second;

			// 조사해볼만한 경로이면 pq에 추가
			if (ans[next] > cost_so_far + cost) {
				ans[next] = cost_so_far + cost;
				pq.push(make_pair(cost_so_far + cost, next));
			}
		}
	}

 

특정 노드를 priority_queue에 넣었다는 것은

계산된 해당 노드까지의 총 가중치가 기존 값보다 작아 조사해볼만한 가치가 있다는 뜻이다

 

즉, 최단거리가 나올 수 있는 가능성이 있는 놈들이 priority_queue에 들어가는 것이다

 

따라서 다음과 같은 if문이 존재해야함

		for (int i = 0; i < graph[curnode].size(); i++) {
			int next = graph[curnode][i].first;
			int cost = graph[curnode][i].second;

			// 조사해볼만한 경로이면 pq에 추가
			if (ans[next] > cost_so_far + cost) {
				ans[next] = cost_so_far + cost;
				pq.push(make_pair(cost_so_far + cost, next));
			}
		}

 

참고로 이 if문을 for문 밖으로 빼면 안되냐고 물어볼 수 있다

 

즉 일단 될 수 있는거 다 우선순위큐에 넣고

우선순위큐에서 pop될때 기존꺼보다 작냐 아니냐를 판단해서 거르면 안되냐 는 것이다

 

하지만 후자는 매우 비효율적이다

BFS DFS할때 visited를 해서 넣는게 아니라 일단 넣고 다음 재귀 들어가서 visited를 체크하는 거랑 똑같은 상황이다!!

 

왜냐하면 쓰레기는 일찍 처리할 수록 좋기 때문이다

쓰레기를 다 모아놓고 거르는 것보다 하나 하나 보면서 쓰레기일때마다 거르는게 훨씬 효율적이다

 

---

 2. 우선순위 큐 내 원소들은 지금까지 계산된 모든 경로들의 집합이다

 

1) 계산된 경로들 중 가장 작은 값인 경로를 뽑아낸다 (pq.top() + pq.pop())

2) 뽑아낸 경로(노드)와 연결된 노드들의 가중치까지 합쳐 조사해볼만 한 것들을 다시 우선순위 큐에 넣는다

 

이렇게 매 순간마다 최적경로값을 뽑아내면서 계속해서 경로를 계산해나가는 것이다

 

그래서 다익스트라는 greedy인 것이다

매순간의 선택이 최적의 결과로 이끄는 선택이 되는 것이기 때문이다!

 

---

3. 필요한 자료구조

 

vector<vector<pair<int,int>>> graph(SIZE) // 간선정보저장용. 2차원 배열
 
priority_queue<pair<int,int>, vector<int,int>, greater<pair<int,int>> pq
// greedy로 풀기 위한 우선순위 큐(heap)
// cost 순으로 정렬해놓기 위해 <cost,end> 순으로 대입
  
int ans[SIZE] // 최단거리 저장 배열. 답 배열

 

---

[다익스트라는 절대 음의 가중치를 계산 못한다??]

 

다익스트라 알고리즘은 항상 음수가 포함된 가중치 그래프의 최단경로를 계산하지 못할까?

정답은 "구할 수도 있고 못 구할 수도 있다."이다.

 

다익스트라는 구현 방법에 따라 음수 가중치를 계산할 수도 못할 수도 있다.

 

Version 1

Using a nested for-loop to relax vertices. This is the easiest way to implement Dijkstra's algorithm. The time complexity is O(V^2).

▶ 중첩 반복문을 사용한 간선 업데이트 구현 방식이다. 우선순위 큐를 사용하지 않는 방식으로 가장 가까운 거리의 노드를 찾고 해당 노드와 연결된 노드들의 최단거리를 갱신한다.

 

Version 2

Priority-queue/heap based implementation + NO re-entrance allowed, where re-entrance means a relaxed vertex can be pushed into the priority-queue again to be relaxed again later.

▶ 우선순위 큐를 사용하되 한 번 방문했던 노드는 절대 다시 방문하지 않는다. 즉 방문한 노드는 우선순위 재삽입하지 않는다. 

 

Version 3

Priority-queue/heap based implementation + re-entrance allowed.

▶ 2번과 유사하지만 한 번 방문한 노드를 다시 우선순위 큐에 삽입하는 것이 가능하다.

 

Version 1 & 2는 음수 가중치가 포함된 그래프의 최단거리를 계산하지 못한다.

반면 Version 3의 경우 노드의 재방문이 허용되므로 음수 가중치에 대한 최단거리를 계산할 수 있다.

 

여기서 알아둬야할 사실은 Version 3과 같이 방문했던 노드를 재방문 하는 것은 굉장히 오버헤드가 크며 노드의 재방문은 전통적인 다익스트라 알고리즘에 부합하지 않는다. 노드의 재방문은 벨만-포드 알고리즘과 더 유사하다고 볼 수 있다. 

 

[참고]

전통적인 다익스트라 알고리즘은 방문한 노드를 다시는 재방문하지 않는다. 다익스트라 알고리즘이 그리디 기반의 알고리즘임을 기억하자.

 

---

#include <iostream>
#include <queue>
#include <vector>

#define SIZE 1001
#define INF int(1e9)

using namespace std;

vector<vector<pair<int, int>>> graph;
int ans[SIZE];

int solve(int start, int end) {
	
	// (cost, start)
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
	pq.push(make_pair(0, start));
	ans[start] = 0;

	while (!pq.empty()) {
		int cost_so_far = pq.top().first;
		int curnode = pq.top().second;
		pq.pop();

		// 조사해볼 필요없으면 skip
		if (cost_so_far > ans[curnode]) continue;

		for (int i = 0; i < graph[curnode].size(); i++) {
			int next = graph[curnode][i].first;
			int cost = graph[curnode][i].second;

			// 조사해볼만한 경로이면 pq에 추가
			if (ans[next] > cost_so_far + cost) {
				ans[next] = cost_so_far + cost;
				pq.push(make_pair(cost_so_far + cost, next));
			}
		}
	}

	return ans[end];
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	
	int N, M;
	cin >> N;
	cin >> M;

	for (int i = 1; i <= N; i++) ans[i] = INF;

	graph = vector<vector<pair<int, int>>>(N + 1);

	int start, end, cost;
	for (int i = 0; i < M; i++) {
		cin >> start >> end >> cost;
		graph[start].push_back(make_pair(end, cost));
	}

	cin >> start >> end;

	cout << solve(start, end);

	return 0;
}