하나의 시작점으로부터 다른 모든 정점까지의 최단 거리를 구하는 알고리즘
우선순위 큐를 이용한 다익스트라 알고리즘의 구현
- 우선순위 큐에 (0, 시작점)을 추가한다
- 우선순위 큐에서 거리가 가장 작은 원소를 선택하고 해당 거리가 최단 거리 테이블에 있는 값과 다른 경우 넘어간다
- 원소가 가리키는 정점을 v라고 할 때, v와 이웃한 정점들에 대해 최단 거리 테이블 값보다 v를 거쳐가는 것이 더 작은 값을 가질 경우 최단 거리 테이블의 값을 갱신하고 우선순위 큐에 (거리, 이웃한 정점의 번호)를 추가한다
- 우선순위 큐가 빌 때 까지 2, 3번을 반복한다
더보기
#include <bits/stdc++.h>
using namespace std;
const int INF = (int)1e9;
vector<int> dist(20001, INF);
vector<pair<int, int>> adj[20001];
int n, m, k;
void dijkstra(int st)
{
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> q;
q.push({ 0, st });
dist[st] = 0;
while (!q.empty())
{
auto cur = q.top(); q.pop();
if (cur.first > dist[cur.second]) continue; // 예제 코드에서는 !=로 처리하던데..
for (auto& nxt : adj[cur.second])
{
int cost = nxt.first + dist[cur.second];
int dest = nxt.second;
if (cost < dist[dest])
{
dist[dest] = cost;
q.push({ cost, nxt.second });
}
}
}
return;
}
int main(void)
{
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n >> m >> k;
while (m--)
{
int u, v, w;
cin >> u >> v >> w;
adj[u].push_back({w, v});
}
dijkstra(k);
for (int i = 1; i <= n; ++i)
{
if (dist[i] != INF) cout << dist[i] << '\n';
else cout << "INF" << '\n';
}
return 0;
}
구현의 핵심 내용
- 최단 거리 테이블 사용 (INF로 초기화)
- 우선순위 큐 사용
- 이미 처리된 간선은 continue로 회피하여 시간복잡도 줄이기
경로 복원
최단거리 테이블을 갱신할 때 pre 테이블도 같이 갱신한다.
이후 도착 정점부터 출발 정점까지 역추적하여 정점들의 방문 순서를 알아낸다.
역추적이기 때문에 역순으로 뒤집어야 출발 정점-도착 정점의 올바른 순서가 된다.
연습 문제
1753: 최단경로
더보기
#include <bits/stdc++.h>
using namespace std;
const int INF = (int)1e9;
vector<int> dist(20001, INF);
vector<pair<int, int>> adj[20001];
int n, m, k;
void dijkstra(int st)
{
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> q;
q.push({ 0, st });
dist[st] = 0;
while (!q.empty())
{
auto cur = q.top(); q.pop();
if (cur.first > dist[cur.second]) continue;
for (auto& nxt : adj[cur.second])
{
int cost = nxt.first + dist[cur.second];
int dest = nxt.second;
if (cost < dist[dest])
{
dist[dest] = cost;
q.push({ cost, nxt.second });
}
}
}
return;
}
int main(void)
{
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n >> m >> k;
while (m--)
{
int u, v, w;
cin >> u >> v >> w;
adj[u].push_back({w, v});
}
dijkstra(k);
for (int i = 1; i <= n; ++i)
{
if (dist[i] != INF) cout << dist[i] << '\n';
else cout << "INF" << '\n';
}
return 0;
}
다익스트라의 구현 코드와 동일하다
11779: 최소비용 구하기2
더보기
#include <bits/stdc++.h>
using namespace std;
const int INF = (int)1e9;
vector<int> dist(1001, INF);
vector<int> path;
vector<pair<int, int>> adj[1001];
int pre[1001];
int n, m, st, en;
void dijkstra(int k)
{
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> q;
q.push({ 0, k });
dist[k] = 0;
while (!q.empty())
{
auto cur = q.top(); q.pop();
if (cur.first > dist[cur.second]) continue;
for (auto& nxt : adj[cur.second])
{
int cost = nxt.first + dist[cur.second];
int dest = nxt.second;
if (cost < dist[dest])
{
dist[dest] = cost;
q.push({ cost, nxt.second });
pre[nxt.second] = cur.second;
}
}
}
return;
}
int main(void)
{
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n >> m;
while (m--)
{
int u, v, w;
cin >> u >> v >> w;
adj[u].push_back({w, v});
}
cin >> st >> en;
dijkstra(st);
int cur = en;
while (cur != st)
{
path.push_back(cur);
cur = pre[cur];
}
path.push_back(st);
reverse(path.begin(), path.end());
cout << dist[en] << '\n';
cout << path.size() << '\n';
for (auto& p : path) cout << p << ' ';
return 0;
}
1-3-5, 1-4-5 둘다 비용이 4로 같기때문에 비교조건을 어떻게 주었냐에 따라 출력이 다를수는 있지만 모두 답으로 인정된다.
경로 추적은 도착지부터 역순으로 이뤄지고 마지막에 출발 정점을 추가하여 뒤집어 출력해야한다.
기본 문제
1238: 파티
더보기
#include <bits/stdc++.h>
using namespace std;
const int INF = (int)1e9;
vector<pair<int, int>> adj[1001];
int n, m, x, mx;
int dijkstra(int st, int en)
{
if (st == en) return 0;
vector<int> dist(1001, INF);
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> q;
q.push({ 0, st });
dist[st] = 0;
while (!q.empty())
{
auto cur = q.top(); q.pop();
if (cur.second == en) return cur.first;
if (cur.first > dist[cur.second]) continue;
for (auto& nxt : adj[cur.second])
{
int cost = nxt.first + dist[cur.second];
int dest = nxt.second;
if (cost < dist[dest])
{
dist[dest] = cost;
q.push({ cost, nxt.second });
}
}
}
}
int main(void)
{
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n >> m >> x;
while (m--)
{
int u, v, w;
cin >> u >> v >> w;
adj[u].push_back({w, v});
}
for (int i = 1; i <= n; ++i)
mx = max(mx, dijkstra(i, x) + dijkstra(x, i));
cout << mx;
return 0;
}
플로이드-워셜같이 출발-도착지를 각각 돌려서 값을 더하면 된다
1504: 특정한 최단 경로
더보기
#include <bits/stdc++.h>
using namespace std;
const int INF = (int)1e9;
vector<pair<int, int>> adj[801];
int n, m, mn, cnt;
int dijkstra(int st, int en)
{
vector<int> dist(1001, INF);
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> q;
q.push({ 0, st });
dist[st] = 0;
while (!q.empty())
{
auto cur = q.top(); q.pop();
if (cur.second == en) return cur.first;
if (cur.first > dist[cur.second]) continue;
for (auto& nxt : adj[cur.second])
{
int cost = nxt.first + dist[cur.second];
int dest = nxt.second;
if (cost < dist[dest])
{
dist[dest] = cost;
q.push({ cost, nxt.second });
}
}
}
cnt++;
return 0;
}
int main(void)
{
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n >> m;
while (m--)
{
int u, v, w;
cin >> u >> v >> w;
adj[u].push_back({ w, v });
adj[v].push_back({ w, u });
}
int v1, v2;
cin >> v1 >> v2;
mn = min(dijkstra(1, v1) + dijkstra(v1, v2) + dijkstra(v2, n),
dijkstra(1, v2) + dijkstra(v2, v1) + dijkstra(v1, n));
if (cnt) cout << -1;
else cout << mn;
return 0;
}
반례를 찾느라 머리가 터지는줄 알았다.
반례의 종류
- 간선이 아예 주어지지 않은 경우
- 두 정점이 연결되어있지 않은 경우 (ex:A,B,C,D에서 A-B, B-C는 간선이 있지만 C-D가 없는경우. 마지막의 경우에서 0이 반환되지만 이미 앞에서 간선들의 비용이 반환되어 합산되기때문에 0으로 처리하면 안됨)
long long을 써서 연결된 간선이 없으면 INF를 반환후 값이 INF 이상이면 -1을 출력하게 하면 쉽게 해결되지만 왠지 모르게 0 반환에 집착하게 되어서 너무 멀리 돌아왔다.
그래서 그냥 0을 반환하게 되는일이 생기면(=간선이 없으면) cnt를 증가시켜서 1이라도 증가되어있으면 -1을 출력하도록 해서 통과했다
'알고리즘 > 바킹독의 실전 알고리즘' 카테고리의 다른 글
| [0x1C] 플로이드-워셜 알고리즘 (0) | 2022.08.10 |
|---|---|
| [0x1B] 최소 신장 트리 (0) | 2022.08.08 |
| [0x1A] 위상 정렬 (0) | 2022.08.08 |
| [0x19] 트리 (0) | 2022.08.08 |
| [0x18] 그래프 (0) | 2022.08.07 |
