[0x1D] 다익스트라 알고리즘

하나의 시작점으로부터 다른 모든 정점까지의 최단 거리를 구하는 알고리즘

 

우선순위 큐를 이용한 다익스트라 알고리즘의 구현

 

1. 우선순위 큐에 (0, 시작점)을 추가한다
2. 우선순위 큐에서 거리가 가장 작은 원소를 선택하고 해당 거리가 최단 거리 테이블에 있는 값과 다른 경우 넘어간다
3. 원소가 가리키는 정점을 v라고 할 때, v와 이웃한 정점들에 대해 최단 거리 테이블 값보다 v를 거쳐가는 것이 더 작은 값을 가질 경우 최단 거리 테이블의 값을 갱신하고 우선순위 큐에 (거리, 이웃한 정점의 번호)를 추가한다
4. 우선순위 큐가 빌 때 까지 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;
}

 

구현의 핵심 내용

1. 최단 거리 테이블 사용 (INF로 초기화)
2. 우선순위 큐 사용
3. 이미 처리된 간선은 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;
}

 

반례를 찾느라 머리가 터지는줄 알았다.

반례의 종류

1. 간선이 아예 주어지지 않은 경우
2. 두 정점이 연결되어있지 않은 경우 (ex:A,B,C,D에서 A-B, B-C는 간선이 있지만 C-D가 없는경우. 마지막의 경우에서 0이 반환되지만 이미 앞에서 간선들의 비용이 반환되어 합산되기때문에 0으로 처리하면 안됨)

 

long long을 써서 연결된 간선이 없으면 INF를 반환후 값이 INF 이상이면 -1을 출력하게 하면 쉽게 해결되지만 왠지 모르게 0 반환에 집착하게 되어서 너무 멀리 돌아왔다.

그래서 그냥 0을 반환하게 되는일이 생기면(=간선이 없으면) cnt를 증가시켜서 1이라도 증가되어있으면 -1을 출력하도록 해서 통과했다