[C++] 플로이드 와샬(Floyd Warshall) 알고리즘 개념

플로이드 와샬 알고리즘이란?

다익스트라 알고리즘이 하나의 정점에서 출발했을 때 다른 모든 정점으로의 최단 경로를 구하는 알고리즘이라면 플로이드 와샬 알고리즘은 모든 정점에서 모든 정점으로의 최단 경로를 구하는 알고리즘입니다.

핵심 아이디어는 거쳐가는 정점을 기준으로 최단 거리를 구하는 것입니다.

 

예시코드

int node[n + 1][n + 1];//입력받기
int dp[n + 1][n + 1];//다이나믹 프로그래밍

void floydWarshall(int n) {

	//그래프 초기화
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <=n ; j++)
			dp[i][j] = node[i][j];
	}

	// k:거쳐가는 노드
	for (int k = 1; k <= n; k++) {
		// i:출발 노드
		for (int i = 1; i <= n; i++) {
			// j:도착 노드
			for (int j = 1; j <= n; j++) {
				if (i == j)
					dp[i][j] = 0;
				else if (dp[i][k] + dp[k][j] < dp[i][j])// 거쳐가는 경우 값이 더 작다면 갱신해줌
					dp[i][j] = dp[i][k] + dp[k][j];
			}
		}
	}

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cout << dp[i][j] << ' ';
		}
		cout << '\n';
	}
}