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

플로이드 워셜 알고리즘

개념

구현 방법

1. 인접 행렬로 구현된 그래프에서 간선이 있으면 비용을 넣고, 간선이 없으면 무한대값을 넣는다.

2. 모든 정점에서 모든 정점까지, 직행하는 경로와 경유하는 경로 중 작은 값을 비용으로 저장한다.

3. 모든 정점을 비교할 수 있게 반복한다.

특징

예시

void FloydWarshall(vector<vector<int>>& map, int n) {
	for (int k = 0; k < n; ++k) { //
		for (int i = 0; i < n; ++i) { //
			for (int j = 0; j < n; ++j) {
				map[i][j] = min(map[i][j], map[i][k] + map[k][j]);
			}
		}
	}
}