실전 알고리즘 0x1C강 - 플로이드 알고리즘

플로이드 알고리즘

[ 알고리즘 설명 ]

- 모든 정점 쌍 사이의 최단 거리를 구하는 알고리즘

- 방향 그래프, 무방향 그래프 모두 동작한다.

- 간선의 값이 음수여도 잘 동작하지만 음수인 사이클이 있으면 문제가 생긴다.

- 시간 복잡도는 O(V^3)이다.

- 정점의 개수가 1,000개 이하로 작으면 시도한다.

 

[ 구현 ]

백준 11404번 : https://www.acmicpc.net/problem/11404

( 3중 for문 )

#include <bits/stdc++.h>
using namespace std;

const int INF = 0x3f3f3f3f;
int v[105][105];

int n, e;
int a, b, c;
int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> e;
	for (int i = 1; i <= n; i++)
		fill(v[i], v[i] + 1 + n, INF);
	for (int i = 0; i < e; i++) {
		cin >> a >> b >> c;
		v[a][b] = min(v[a][b],c);
	}
	for (int i = 1; i <= n; i++) v[i][i] = 0;
	
	for (int k = 1; k <= n; k++)
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++)
				v[i][j] = min(v[i][j], v[i][k] + v[k][j]); // if 문으로 바꾸면 시간을 줄일 수 있다.

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

 

[ 경로 복원 방법 ]

- V x V 배열을 하나두어 최단거리 배열이 갱신될 때마다 경로 복원 배열의 값을 갱신해준다.

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (v[i][j] == 0 || v[i][j] == INF) {
				cout << "0\n";
				continue;
			}
			vector<int> path;
			int st = i;
			while (st != j) {
				path.push_back(st);
				st = nxt[st][j];
			}
			path.push_back(j);
			cout << path.size() << ' ';
			for (auto x : path) cout << x << ' ';
			cout << '\n';
		}
	}