플로이드 - 와샬 알고리즘

플로이드 와샬 알고리즘은 다익스트라, 벨만 포드 알고리즘과 달리 '모든 정점에서 다른 정점까지의 최단거리'를 구한다.

 

다익스트라처럼 큐에 넣어서 거쳐가는 지점을 뽑아 쓰는 것과 달리 플로이드 와샬은

거쳐가는 지점을 중심으로 해서 다시 모든 노드를 탐색한다. 따라서 시간 복잡도는 \(O(N^3)\) 이 걸린다.

 

www.acmicpc.net/problem/11404

11404번: 플로이드

 

문제 풀이를 통해 알아보면 시간 복잡도가 높은 만큼 입력 범위는 작게 100으로 주어진다.

 

	for (int k = 0; k < n; k++) { //k = 거처가는 노드
		for (int i = 0; i < n; i++) { // i = 시작 노드
			for (int j = 0; j < n; j++) { // j = 도착 노드
				d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
				//i -> j = min(시작 -> 도착, 시작 -> 거처가는 노드 + 거처가는 노드 -> 도착 노드)
			}
		}
	}

 

놀랍지만 저 코드가 플로이드 와샬 알고리즘을 나타낸다. 

중간에 거쳐가는 모든 노드에 대해 각 정점들을 전부 탐색하다 보니 다익스트라는 1차원 배열을 사용하지만

플로이드 와샬은 2차원 배열을 사용하여 i -> j로 가는 최단거리를 모두 나타낸다.

 

다익스트라나 벨만 포드와 달리 모든 정점을 INF로 초기화하지 않고 i == j 인 부분에 대해 0으로 처리해준다.

 

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			d[i][j] = i == j ? 0 : INF;
		}
	}

 

자기 자신으로 가는 최단거리는 0이므로 d [i][i]인 모든 부분을 0으로 초기화해줘야 한다.

 

#include <iostream>
using namespace std;

const int INF = 1e9;
int d[101][101];
int n, m, a, b, c;

int min(int a, int b) { return a > b ? b : a; }

int main() {
	ios::sync_with_stdio(false); cin.tie(0);

	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			d[i][j] = i == j ? 0 : INF;
		}
	}

	for (int i = 0; i < m; i++) {
		cin >> a >> b >> c;
		d[a - 1][b - 1] = min(d[a - 1][b - 1], c);
	}

	for (int k = 0; k < n; k++) { //k = 거처가는 노드
		for (int i = 0; i < n; i++) { // i = 시작 노드
			for (int j = 0; j < n; j++) { // j = 도착 노드
				d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
				//i -> j = min(시작 -> 도착, 시작 -> 거처가는 노드 + 거처가는 노드 -> 도착 노드)
			}
		}
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (d[i][j] >= INF) cout << 0 << ' ';
			else cout << d[i][j] << ' ';
		}
		cout << '\n';
	}

	return 0;
}