[C++] 플로이드-워셜(Floyd-warshall)

 

 

 

플로이드-워셜(Floyd-warshall) 알고리즘은 모든 노드에 대해 그래프에서 최단 거리를 구하는 알고리즘이다. 이 알고리즘의 특징은 다음과 같다.

• 음수 가중치가 있어도 수행할 수 있다.
• 동적 계획법(Dynamic Programming) 원리를 따른다.
• 시간 복잡도는 O(V ^ 3)으로 많이 느린 편에 속한다.

그래서 N이 1000개 이상인 경우에는 사용하기 어렵다.

 

 

 

 

 

플로이드-워셜 자료구조

먼저 그래프를 표현할 인접 행렬이 필요하다. 인접 행렬은 2개의 노드 인덱스와, 1개의 거리 요소로 구성되어 있다. 이 자료구조 하나로 플로이드-워셜 알고리즘을 구현할 수 있다.

 

 

 

 

 

플로이드-워셜 원리

플로이드-워셜의 핵심 원리는 A 노드에서 B 노드까지 최단 경로를 구했다고 가정했을 때 최단 경로 위에 K 노드가 존재한다면 그것을 이루는 부분 경로 역시 최단 경로라는 것이다.

 

예를 들어, 1 -> 5 최단 경로를 살펴보면 1 -> 4 최단 경로와 4 -> 5 최단 경로 역시 1 -> 5 최단 경로로 이뤄질 수 밖에 없다. 따라서 전체 최단 경로는 부분 경로의 최단 경로 조합으로 이뤄진다.

 

이 원리는 따라 다음과 같은 점화식을 만들 수 있다.

 

D[S][E] = min(D[S][E], D[S][K] + D[K][E])

 

 

 

 

먼저 인접 행렬을 초기화한다. 시작과 끝이 같은 D는 0으로, 다른 D는 Dummy로 초기화한다.

 

 

 

 

그 후 그래프를 인접 행렬에 저장한다.

 

 

 

 

3중 for loop을 통해 모든 경우를 탐색한다.

이제 원리에 맞춰 점화식을 코드로 구현하면 끝이다.

 

 

 

 

 

플로이드-워셜 코드 (백준 11404: 플로이드)

https://www.acmicpc.net/problem/11404

11404번: 플로이드

#include <iostream>
#include <vector>
#include <queue>

#define DUMMY 1e9+7

using namespace std;

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

	int N, M;
	cin >> N >> M;
	vector<vector<int>> matrix(N + 1, vector<int>(N + 1, DUMMY));

	for (int i = 1; i <= N; i++)
		matrix[i][i] = 0;

	for (int i = 0; i < M; i++)
	{
		int start, end, weight;
		cin >> start >> end >> weight;
		if (matrix[start][end] > weight)
			matrix[start][end] = weight;
	}

	for (int k = 1; k <= N; k++)
		for (int s = 1; s <= N; s++)
			for (int e = 1; e <= N; e++)
				matrix[s][e] = min(matrix[s][e], matrix[s][k] + matrix[k][e]);

	for (int s = 1; s <= N; s++)
	{
		for (int e = 1; e <= N; e++)
		{
			if (matrix[s][e] == DUMMY)
				matrix[s][e] = 0;
			cout << matrix[s][e] << ' ';
		}
		cout << '\n';
	}

	return 0;
}