#include <iostream>
#include <queue>
#include <vector>
using namespace std;
#define INF 1e9;
vector<pair<int, int>> v[1001];
priority_queue <pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>> > pq;
int dist[1001];
int n, m, from, to, fromToCost, start, dest;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
for (int i = 0; i < m; i++) {
cin >> from >> to >> fromToCost;
v[from].push_back(make_pair(to, fromToCost));
}
cin >> start >> dest;
for (int i = 0; i <= n; i++) {
dist[i] = INF;
}
dist[start] = 0;
pq.push(make_pair(0, start));
while (!pq.empty()) {
int distance = pq.top().first;
int here = pq.top().second;
pq.pop();
for (int i = 0; i < v[here].size(); i++) {
int next = v[here][i].first;
int cost = v[here][i].second + distance;
if (dist[next] > cost) {
dist[next] = cost;
pq.push(make_pair(dist[next], next));
}
}
}
cout << dist[dest];
}
다익스트라 알고리즘은 최소 비용을 구하는 알고리즘 중에 시작 노드에서 도착 노드까지의 최소 비용을 구할 수 있는 알고리즘이다.
- 초기화해줄 내용은 비용 기록 배열을 시작 노드 빼고 모두 임의의 큰 값(INF)으로 초기화해주고, 우선순위 큐를 이용해서 방문 노드의 연결된 노드 중에 비용이 가장 작은 노드를 O(E*logN)의 시간 복잡도로 선택했다는 것이다.
(우선순위 큐의 삽입, 삭제 O(logN)를 모든 간선의 크기 E만큼)
만약 우선순위 큐를 사용하지 않으면 매번 비용이 가장 작은 노드를 선형 탐색을 해야 하므로 O(n^2)의 시간 복잡도가 나올 것이다. (n = 정점의 수)
- 알고리즘
1. 시작 노드에서 연결된 각각의 노드에 대해 비용을 업데이트해주고, 시작 노드를 방문한 노드로 체크한다.
(한번 방문한 노드는 더 이상 최소 비용을 업데이트해주지 않는다.)
2. 방문 노드와 연결된 노드 중 비용이 가장 작은 노드를 선택해서 해당 노드를 방문한다.
3. 방문 노드의 비용을 이전 노드 + 간선 비용보다 크면 작은 값으로 업데이트해준다.
4. 탐색이 끝날 때까지 2와 3의 과정을 반복해준다.
5. 도착 노드의 최소 비용은 해당 노드의 최종 업데이트 값에 해당된다.
- 한번 방문한 노드를 더 이상 최소 비용을 업데이트해주지 않는다면, 다른 구간을 통해 방문할 경우 그보다 더 작은 비용이 발생할 수도 있지 않을까?
-> 항상 탐색을 할 경우 방문 노드에서의 비용이 가장 작은 노드를 선택하기 때문에 가능하다.
노드가 A, B, C가 있다고 하면 만약 비용이 가장 작은 노드 A ( A-B)를 선택했는데 이것이 최소 비용이 아니라면 방문 노드에서 비용이 가장 작은 노드를 선택할 때 C를 통해서 B에게 가는 경우 (A-C-B)가 더 작은 비용이어야 한다.
즉 A-B > A-C 가 성립되어야 하는데 이렇게 되면 애초에 최소비용을 선택할 때 (A-B)를 선택한 것이 모순이 된다.
따라서 방문했을 때 업데이트해준 값이 최소 비용이 되고 이 모든 가정은 간선 비용이 양수 일 때만 가능하다.
(음수가 포함될 경우 A-B < A-C 이어도 C-B가 음수 값이면 최종적으로 A-B > A-C-B 가 가능하기 때문이다.)
'문제 풀이 > 백준 알고리즘' 카테고리의 다른 글
[baekjoon 1912] 연속합 - DP(동적 프로그래밍) (C++) (0) | 2021.01.26 |
---|---|
[baekjoon 2579] 계단 오르기 - DP(동적 프로그래밍) (C++) (0) | 2021.01.16 |
[baekjoon 9095] 1, 2, 3 더하기 - DP(동적 프로그래밍) (C++) (0) | 2021.01.11 |
[baekjoon 18870] 좌표 압축 - 정렬, 값 압축 (C++) (0) | 2021.01.08 |
[baekjoon 11726] 2xN 타일링- DP(동적 프로그래밍) (C++) (0) | 2021.01.03 |