[2022 1학기] 5주차 - 플로이드-와샬

1. 플로이드-와샬이란?

다익스트라 알고리즘과 같이 최단 거리를 구할 수 있는 알고리즘

모든 정점에서 모든 정점으로의 최단 경로를 한번에 구하는 알고리즘

모든 쌍을 행렬로 선언하고 DP를 이용해 각 쌍의 최단 거리를 업데이트한다

거쳐가는 정점을 기준으로 최단 거리를 업데이트한다.

 

2. 동작 원리

정점 i에서 정점 j까의 최단 경로

dp[i][j] = min(dp[i][j], dp[i][n] + dp[n][j])

n -> 경유점

i에서 j로 곧바로 가는 경우 vs i에서 다른 정점 k를 거쳐 j로 가는 경로

 

3. 코드

void floyd() {
	for (int k = 0; k < N; k++) {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				arr[i][j] = min(arr[i][j], arr[i][k] + arr[k][j]);
			}
		}
	}
}

void init() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (i == j)
				arr[i][j] = 0;
			else
				arr[i][j] = INF;
		}
	}
}

 

 

※공부 중 작성한 내용이기에 틀린 부분이 있을 수도 있습니다!