플로이드

1. 플로이드 알고리즘

---

모든 정점 쌍 사이의 최단 거리를 구하는 알고리즘

• 방향 그래프나 무방향 그래프 모두 상관없음
• 간선이 음수여도 동작함, 단 음수 사이클은 없어야 함
• 시간 복잡도는 O(V^3)

왜 쓸까?

• 예를 들어 정점이 100개 정도일 때 쓸만함 -> 코드가 쉬우니까
• 모든 정점에 대한 거리를 알고 싶을 때 
• 경유지를 고려해야 할 때 (다익스트라 같은 경우는 A->Z 까지의 최단 거리만 구하기 때문)
• 또한 음수 가중치가 있는 경우..

 

2. 동작 방식

---

• 먼저 테이블을 만들어 두고, 각 정점에서 인접한 정점까지의 거리만 업데이트하여 최단 거리 테이블을 만든다.

• 지금까지 적어둔 값은 어떠한 정점을 거치지 않았을 때의 모습이다. 이제부터는 특정 정점을 거쳐가면서 더 짧은 경로가 있다면 업데이트 해주면 된다.
• 아래 모습은 정점 1은 거쳐가는 경우 업데이트된 최단 거리 테이블의 모습이다

• 위에서 한 방식을 모든 정점을 다 돌면서 수행하면 된다.
• 코드로 생각해보면 업데이트 하는 부분에 있어서는 dp 방식과 유사한 비교를 하게 되는데, s에서 t로 가는동안 n을 지난다고 했을때 아래와 같은 코드를 통해 업데이트 하게 된다.

DP[s][t] = min(DP[s][t], DP[s][n] + DP[n][t]);

 

• 모든 정점에 대해서 V 단계에 걸쳐서 갱신이 이루어지고, 각 단계마다 V^2개의 DP 값을 비교하기 때문에 시간 복잡도는 O(V^3) 이 된다.

 

3. 코드

---

주의점

• 두 거리 덧셈에 있어서 int overflow 방지를 위해서 INF값 설정하기
• 플로이드는 대충 정점 1000개까지는 해볼만 하다...
• 비교하는 부분에서 min 함수를 쓰기보다 if문으로 체크하는 방식으로 바꾸면 좀 더 효율적이다
  • 이유는 대입을 매번 하는 것을 막을 수 있기 때문이다.
• boj 11404 풀이

#include <iostream>
#include <climits>
using namespace std;

int n, m;
int arr[102][102];
const int INF = 0x3f3f3f3f;

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

	cin >> n;
	cin >> m;
	
	for (int i = 1; i <= n; ++i)
		fill(arr[i], arr[i] + 1 + n, INF);

	for (int i = 1; i <= n; ++i)
	{
		arr[i][i] = 0;
	}

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

	for (int i = 1; i <= n; ++i)
	{
		for (int j = 1; j <= n; ++j)
		{
			for (int k = 1; k <= n; ++k)
			{
				arr[j][k] = min(arr[j][k], arr[j][i] + arr[i][k]);
			}
		}
	}

	for (int i = 1; i <= n; ++i)
	{
		for (int j = 1; j <= n; ++j)
		{
			if (arr[i][j] == INF)
				cout << "0 ";
			else
				cout << arr[i][j] << " ";
		}
		cout << "\n";
	}
}

 

• 추가) 사이클 구하기 (boj 1956)

#include <iostream>
using namespace std;

int board[402][402];
const int INF = 0x3f3f3f3f;
int v, e;
int answer = INF;

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

	cin >> v >> e;
	for (int i = 1; i <= v; ++i)
		fill(board[i] + 1, board[i] + 1 + v, INF);

	for (int i = 1; i <= v; ++i)
		board[i][i] = 0;

	for (int i = 0; i < e; ++i)
	{
		int a, b, c;
		cin >> a >> b >> c;
		board[a][b] = c;
	}

	for (int i = 1; i <= v; ++i)
	{
		for (int j = 1; j <= v; ++j)
		{
			for (int k = 1; k <= v; ++k)
			{
				board[j][k] = min(board[j][k], board[j][i] + board[i][k]);
			}
		}
	}

	//사이클 계산
	for (int i = 1; i <= v; ++i)
	{
		for (int j = i + 1; j <= v; ++j)
		{
			answer = min(answer, board[i][j] + board[j][i]);
		}
	}

	if (answer == INF)
		cout << -1;
	else
		cout << answer;
}