[0x1C] 플로이드-워셜 알고리즘

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

 

방향, 무방향에 상관없이 사용할 수 있고 간선의 값이 음수여도 사용 가능하지만 간선의 값이 음수인 사이클이 있으면 문제가 생긴다.

 

경로 복원

 

플로이드-워셜 알고리즘으로 생성된 최단거리 테이블만으로는 어떤 경로가 최단거리인지 바로 알 수 없다.

 

최단거리 테이블을 D, 경로 테이블을 nxt라고 할 때,

D[i][j]로 가는 경로보다 D[i][k] + D[k][j]의 경로가 더 짧다면 D[i][j]를 갱신함과 동시에 nxt[i][j]를 nxt[i][k]로 갱신한다.

 

연습 문제

 

11404: 플로이드

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

const int INF = (int)1e9;
int t[101][101];
int n, m;

int main(void)
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	cin >> n >> m;
	for (int i = 1; i <= n; ++i)
	{
		fill(t[i] + 1, t[i] + n + 1, INF);
		t[i][i] = 0;
	}
	while (m--)
	{
		int a, b, c;
		cin >> a >> b >> c;
		t[a][b] = min(t[a][b], c); // 같은 간선이 여러개일수도 있음
	}
	for (int k = 1; k <= n; ++k)
	{
		for (int i = 1; i <= n; ++i)
		{
			for (int j = 1; j <= n; ++j)
				t[i][j] = min(t[i][j], t[i][k] + t[k][j]);
		}
	}
	for (int i = 1; i <= n; ++i)
	{
		for (int j = 1; j <= n; ++j)
		{
			if (t[i][j] != INF) cout << t[i][j] << ' ';
			else cout << 0 << ' ';
		}
		cout << '\n';
	}
	return 0;
}

 

플로이드-워셜 알고리즘의 전형적인 구현 방법

 

11780: 플로이드 2

추가 작성 예정