[C++] 최단 경로(다익스트라, 플로이드 와샬, 벨만 포드)

최단 경로

두 정점 사이의 경로 중 간선의 가중치 합이 최소인 경로를 찾는 알고리즘이다.

 

1. 다익스트라 알고리즘

가중치가 적은 순서대로 그 정점에 연결된 정점을 방문하면서 값을 갱신하는 알고리즘이다.

• 음의 가중치를 가진 경로는 구할 수 없다.
• 가중치 합의 최댓값은 가중치 최댓값 * (정점 개수 - 1) 이다.

 

1) 문제

 

https://www.acmicpc.net/problem/1753

1753번: 최단경로

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

const int INF = 1e9;

vector<pair<int, int>> graph[20001];
int dist[20001];

int main()
{
	int V, E, K;
	cin >> V >> E >> K;
	for (int i = 1, u, v, w; i <= E; i++) {
		cin >> u >> v >> w;
		graph[u].push_back(make_pair(v, w));
	}

	for (int i = 1; i <= V; i++)
		dist[i] = INF;

	priority_queue<pair<int, int>> pq;
	pq.push(make_pair(0, K)); // 가중치, 정점
	dist[K] = 0;
	while (!pq.empty()) {
		int tv = pq.top().second;
		int tw = -pq.top().first;
		pq.pop();

		for (int i = 0; i < graph[tv].size(); i++) {
			int nv = graph[tv][i].first;
			int nw = tw + graph[tv][i].second;

			if (nw < dist[nv]) {
				dist[nv] = nw;
				pq.push(make_pair(-nw, nv));
			}
		}
	}

	for (int i = 1; i <= V; i++) {
		if (dist[i] == INF)
			cout << "INF\n";
		else
			cout << dist[i] << "\n";
	}
}

 

https://www.acmicpc.net/problem/1504

1504번: 특정한 최단 경로

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

const int INF = 1e9;

int V, E;
vector<pair<int, int>> graph[801];
long long dist[801];

void Dijkstra(int start)
{
	for (int i = 1; i <= V; i++)
		dist[i] = INF;

	priority_queue<pair<int, int>> pq;
	pq.push(make_pair(0, start));
	dist[start] = 0;
	while (!pq.empty()) {
		int tv = pq.top().second;
		int tw = -pq.top().first;
		pq.pop();

		for (int i = 0; i < graph[tv].size(); i++) {
			int nv = graph[tv][i].first;
			int nw = tw + graph[tv][i].second;

			if (nw < dist[nv]) {
				dist[nv] = nw;
				pq.push(make_pair(-nw, nv));
			}
		}
	}
}

int main()
{
	cin >> V >> E;
	for (int i = 0, a, b, c; i < E; i++) {
		cin >> a >> b >> c;
		graph[a].push_back({ b, c });
		graph[b].push_back({ a, c });
	}

	int v1, v2;
	cin >> v1 >> v2;

	// res1: 1 -> v1 -> v2 -> v
	// res2: 1 -> v2 -> v1 -> v
	long long res1 = 0, res2 = 0;
	Dijkstra(1);
	res1 += dist[v1], res2 += dist[v2];
	Dijkstra(v1);
	res1 += dist[v2], res2 += dist[V];
	Dijkstra(v2);
	res1 += dist[V], res2 += dist[v1];

	res1 = res1 < res2 ? res1 : res2;
	if (res1 >= INF)
		cout << -1;
	else
		cout << res1;
}

 

2. 플로이드 와샬 알고리즘

거쳐가는 지점이 달라질 때마다 최솟값을 갱신하는 알고리즘이다. A→B로 갈 때, A→B보다 A→C→B와 같이 C를 거쳐가는 경우가 더 최솟값이라면 갱신한다.

 

1) 문제

 

https://www.acmicpc.net/problem/11404

11404번: 플로이드

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

const int INF = 1e9;

int graph[101][101];

int main()
{
	int N, M;
	cin >> N >> M;
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= N; j++)
			graph[i][j] = INF;
	for (int i = 0, a, b, c; i < M; i++) {
		cin >> a >> b >> c;
		if (c < graph[a][b])
			graph[a][b] = c;
	}

	for (int k = 1; k <= N; k++) // 거쳐가는 노드
		for (int i = 1; i <= N; i++) // 출발
			for (int j = 1; j <= N; j++) // 도착
				if (graph[i][k] + graph[k][j] < graph[i][j])
					graph[i][j] = graph[i][k] + graph[k][j];

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (i == j || graph[i][j] == INF)
				cout << "0 ";
			else
				cout << graph[i][j] << " ";
		}
		cout << "\n";
	}
}

 

https://www.acmicpc.net/problem/1956

1956번: 운동

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

int INF = 1e9;

int graph[401][401];

int main()
{
	int V, E;
	cin >> V >> E;
	for (int i = 1; i <= V; i++)
		for (int j = 1; j <= V; j++)
			graph[i][j] = INF;
	for (int i = 1, a, b, c; i <= E; i++) {
		cin >> a >> b >> c;
		graph[a][b] = c;
	}

	for (int k = 1; k <= V; k++)
		for (int i = 1; i <= V; i++)
			for (int j = 1; j <= V; j++)
				if (graph[i][k] + graph[k][j] < graph[i][j])
					graph[i][j] = graph[i][k] + graph[k][j];

	int ans = INF;
	for (int i = 1; i <= V; i++)
		ans = min(ans, graph[i][i]);
	if (ans == INF) 
		cout << -1;
	else 
		cout << ans;
}

 

3. 벨만 포드 알고리즘

• 음의 가중치를 허용하지만 음의 사이클은 허용하지 않는다.
• 최단 경로를 구하는 과정을 N번 더 반복하고 N번째에 최단거리가 갱신된다면 음의 사이클이라고 간주한다.

 

1) 문제

 

https://www.acmicpc.net/problem/11657

11657번: 타임머신

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

int main()
{
	int N, M;
	cin >> N >> M;

	vector<pair<int, int>> v[501];
	for (int i = 0, A, B, C; i < M; i++) {
		cin >> A >> B >> C;
		v[A].push_back({ B, C });
	}

	long long dist[501];
	fill(dist, dist + N + 1, 1e9);
	dist[1] = 0;

	bool flag = false;
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= N; j++) {
			if (dist[j] == 1e9)
				continue;

			for (auto& k : v[j]) {
				if (dist[j] + k.second < dist[k.first]) {
					dist[k.first] = dist[j] + k.second;

					if (i == N)
						flag = true;
				}
			}
		}

	if (flag)
		cout << -1;
	else {
		for (int i = 2; i <= N; i++)
			printf("%lld\n", dist[i] == 1e9 ? -1 : dist[i]);
	}
}

 

www.acmicpc.net/problem/1865

1865번: 웜홀

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

int main()
{
	int T;
	cin >> T;
	while (T--) {
		int n, m, w;
		cin >> n >> m >> w;

		vector<pair<int, int>> v[501];
		for (int i = 0; i < m; ++i) {
			int s, e, t;
			cin >> s >> e >> t;
			v[s].push_back({ e, t });
			v[e].push_back({ s, t });
		}
		for (int i = 0; i < w; ++i) {
			int s, e, t;
			cin >> s >> e >> t;
			v[s].push_back({ e, -t });
		}

		int dist[501];
		fill(dist, dist + 501, 1e9);
		dist[1] = 0;

		bool flag = false;
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++) {
				for (auto& k : v[j]) {
					if (dist[j] + k.second < dist[k.first]) {
						dist[k.first] = dist[j] + k.second;

						if (i == n)
							flag = true;
					}
				}
			}

		cout << (flag == true ? "YES\n" : "NO\n");
	}
}