플로이드-워셜 알고리즘

플로이드-워셜 알고리즘

이 알고리즘은 그래프에서 최단 거리를 구하는 알고리즘이다.

이름은 어려워 보이지만 그냥 이 알고리즘을 개발한 사람의 이름을 딴 거라고 한다.

동적 계획법을 활용하는 그래프 최단거리 알고리즘이며, 시간 복잡도가 O(V^3)이라는 느리다는 특징을 기억하자.

 

• 기능
  • 모든 노드 간에 최단 경로 탐색
• 특징
  • 음수 가중치 에지가 있어도 수행할 수 있음
  • 동적 계획법의 원리를 이용해 알고리즘에 접근
• 시간 복잡도
  • O(V^3)

 

핵심 알고리즘

 

앞서 배웠던 벨만-포드와 유사하지만 둘의 차이는 벨만 포드는 하나의 시작점과 이외의 모든 노드의 최단 거리를 구하는 것다.

플로이드 워셜은 그래프의 모든 노드쌍에 대해서 최단 거리를 구하는 알고리즘이다.

 

• 단일 시작점 최단 경로 → 벨만-포드
• 모든 쌍 최단 경로 → 플로이드-워셜
• 노드 수가 많고 간선이 적음 → 벨만-포드
• 노드 수가 적고 간선이 많음 → 플로이드-워셜

 

백준 11404번 : 플로이드

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

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

int n, m;

constexpr long long MAX_VAL = 10000000000;
long long graph[101][101];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	cin >> n >> m;

	//그래프의 모든 값을 무한대로 하기
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			if (i == j)
			{
				graph[i][j] = 0;
			}
			else
			{
				graph[i][j] = MAX_VAL;
			}
		}
	}

	//그래프 표현
	for (int i = 0; i < m; i++)
	{
		long long s, e, w;
		cin >> s >> e >> w;

		//두 정점을 잇는 간선이 다수 일 수 있으니 최단 거리를 넣는다.
		if (graph[s][e] > w)
		{
			graph[s][e] = w;
		}
	}

	//플로이드 워셜
	for (int k = 1; k <= n; k++)
	{
		for (int s = 1; s <= n; s++)
		{
			for (int e = 1; e <= n; e++)
			{
				graph[s][e] = min(graph[s][e], graph[s][k] + graph[k][e]);
			}
		}
	}
	
    //결과 출력
	for (int s = 1; s <= n; s++)
	{
		for (int e = 1; e <= n; e++)
		{
			if (graph[s][e] == MAX_VAL)
			{
				cout << 0 << ' ';
			}
			else
			{
				cout << graph[s][e] << ' ';
			}
		}
		cout << '\n';
	}

	return 0;
}

 

이 문제는 모든 노드 쌍의 최단거리를 구하는 문제이기 때문에 플로이드 워셜을 적용하면 풀 수 있다.

노드가 1부터 시작한다는 점에 주의!

 

백준 11403 : 경로 찾기

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

#include <iostream>
using namespace std;

int N;
int D[100][100];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	cin >> N;

	//그래프 입력 받기
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			cin >> D[i][j];
		}
	}

	for (int k = 0; k < N; k++)
	{
		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < N; j++)
			{
				//i와 j 사이의 경로 여부는 임의의 k에 대해서  (i, k), (k, j)사이의 경로가 둘다 존재 하면 존재한다.
				if(D[i][k] == 1 && D[k][j] == 1)
					D[i][j] = 1;
			}
		}
	}
	//결과 출력
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			cout << D[i][j] << ' ';
		}
		cout << '\n';
	}

	return 0;
}

 

이 문제는 모든 노드 쌍을 조사해서 임의의 노드간의 경로가 있는지 조사해야 한다.

노드의 수가 100개가 최대이므로 시간 복잡도를 고려해도 플로이드-워셜 알고리즘을 적용하면 풀 수 있다.

i, j 노드 사이의 경로가 존재하려면 임의의 노드 k에 대해서 i,k/k,j 이 두 쌍의 경로가 존재해야 한다.

그 점을 이해하고 구현하면 간단하게 풀 수 있다.

 

백준 1389번 : 케빈 베이컨의 6단계 법칙

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

#include <iostream>
using namespace std;

int N, M;
int D[101][101];
constexpr int MAX_VAL = 5001;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	cin >> N >> M;

	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= N; j++)
		{
			if (i == j)
				D[i][j] == 0;
			else
				D[i][j] = MAX_VAL;
		}
	}

	//그래프 입력 받기
	for (int i = 0; i < M; i++)
	{
		int s, e;
		cin >> s >> e;
		D[s][e] = 1;
		D[e][s] = 1;
	}

	//플로이드 워셜 알고리즘
	//모든 노드 쌍의 최단 거리 구하기
	for (int k = 1; k <= N; k++)
	{
		for (int i = 1; i <= N; i++)
		{
			for (int j = 1; j <= N; j++)
			{
				D[i][j] = min(D[i][j], D[i][k] + D[k][j]);
			}
		}
	}

	//각 노드의 케빈 구해서 제일 작은 케빈 구하고 그 사람 출력
	int minKebin = MAX_VAL;
	int answer = 0;
	for (int i = 1; i <= N; i++)
	{
		int tempKabin = 0;
		for (int j = 1; j <= N; j++)
		{
			tempKabin += D[i][j];
		}
		if (tempKabin < minKebin)
		{
			minKebin = tempKabin;
			answer = i;
		}
	}

	cout << answer;
	return 0;
}

 

문제가 너무 길지만, 차분히 이해하면 모든 간선의 가중치가 1이고 모든 사람 쌍의 최단 거리를 구해서 한 노드에서 출발한 다른 모든 경로에서의 값의 합이 가장 작은 사람을 출력하면 되는 문제이다.

 

문제 조건을 보고 플로이드 워셜을 떠올릴 수 있다.

모든 노드 쌍의 최단 거리를 구해야 하기 때문이고, 노드 수도 100밖에 되지 않아 충분하기 때문이다.

 

공부 자료: Do it! 알고리즘 코딩 테스트(김종관, 이지스퍼블리싱)