플로이드 와샬 알고리즘을 사용하는 이유

모든 정점으로 시작하여 모든 정점까지의 최단 거리를 찾기 위해서 사용한다.
참고로 다익스트라 알고리즘은 한 정점으로 시작하여 모든 정점까지의 최단 거리를 찾을 때 사용한다.

플로이드 와샬

• 거쳐가는 정점을 기준으로 진행된다.
• DP의 일종으로 2차원 배열을 사용한다.
• 거쳐가는 정점을 거쳐가는 것이 더 효율적인지 아니면 거치지 않는게 더 효율적인지 비교하여 더 효율적인 것을 DP 배열에 저장한다.
• 맨처음 DP 배열을 초기화할 때 (1, 1)과 같이 자기 자신을 시작, 도착 노드로 하는 경우에는 값을 0으로 하고 바로 갈 수 없는 경우에는 INF로 무한으로 초기화한다. 이때 INF를 실제 정수의 최대값인 21억으로 할 경우 나중에 계산 과정에서 INF + x를 하여 오버플로우되어 음수가 되어 제대로된 비교를 할 수 없으니 100,000,000 정도로 충분히 크지만 어떤 수를 더했을 때 오버플로우 되지 않도록 주의해야한다.

플로이드 와샬 알고리즘 코드

// 자기 자신을 시작, 도착 노드인 경우 0으로 DP 배열을 초기화
// 바로 갈 수 없는 경우 INF로 DP 배열을 초기화
//n은 정점의 개수
void floyd_warshall(int n) {
	// 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 (dp[i][k] + dp[k][j] < dp[i][j]) { //k를 거처가는 것이 비용이 덜 든다면 값 갱신
					dp[i][j] = dp[i][k] + dp[k][j];
				}
			}
		}
	}
}

참고 예제

백준 11404번 플로이드

📝 문제

📌 풀이

1. 모든 경로를 무한으로 초기화한다.
2. 자기 자신을 시작, 도착으로 가지면 거리를 0으로 초기화한다.
3. 시작-도착 노선과 비용을 입력 받고 만약 같은 노선의 여러 버스가 있다면 최소 값만을 초기화한다.
4. 플로이드-마샬 알고리즘을 수행한다.
5. 결과 DP 배열을 출력하고 이 때 여전히 INF 값을 가진다면 갈 수 없는 경우이므로 0을 출력한다.

💻 코드

//난이도 : 골드4
//시작 : 09:26
//끝 : 09:46
#include <iostream>
#include <limits>

using namespace std;

#define INF 100000000 //무한 값 정의

int dp[101][101] = { 0 };

//n은 정점의 개수
void floyd_warshall(int n) {
	// 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 (dp[i][k] + dp[k][j] < dp[i][j]) { //k를 거처가는 것이 비용이 덜 든다면 값 갱신
					dp[i][j] = dp[i][k] + dp[k][j];
				}
			}
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	//모든 경로를 무한으로 초기화
	for (int i = 0; i < 101; i++) {
		for (int j = 0; j < 101; j++) {
			dp[i][j] = INF;
		}
	}

	int n, m;
	cin >> n >> m;

	//자기 자신을 시작, 도착으로 가지면 거리는 0이다.
	for (int i = 1; i <= n; i++) {
		dp[i][i] = 0;
	}

	for (int i = 0; i < m; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		if (dp[a][b] > c) { // 최소 거리만 갱신 //같은 구간을 연결하는 노선이 하나가 아닐 수 있기 때문
			dp[a][b] = c;
		}
	}

	// 플로이드-마샬 알고리즘 수행
	floyd_warshall(n);

	//결과 출력
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (dp[i][j] == INF) { //여전히 갈 수 없는 경우
				dp[i][j] = 0; //0으로 출력
				cout << dp[i][j] << " ";
			}
			else {
				cout << dp[i][j] << " ";
			}
		}
		cout << '\n';
	}


	return 0;
}

참고 자료

안경잡이 개발자 - 실전 알고리즘 강좌