플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)

목차

1. 플로이드-워셜 알고리즘이란?
2. 알고리즘 사용 예시
3. 불가능한 예시
4. 시간 복잡도

1. 플로이드 워셜 알고리즘이란?

앞서 살펴 보았던 최단 거리 알고리즘들은 시작 정점이 정해져야 했습니다.
플로이드 워셜 알고리즘은 시작 지점을 설정하지 않습니다.
플로이드 워셜 알고리즘은 모든 정점사이의 최단거리를 구하는 과정에 사용됩니다.

2. 알고리즘 사용 예시

위 그래프를 사용하여 예시를 들어보겠습니다.

int n = v.size();
for (int k = 1; k <= n; k++)
	for (int i = 1; i <= n; i++)
    		for (int j = 1; j<= n; j++)
            		if (D[i][j] > D[i][k] + D[k][j])
                    		D[i][j] = D[i][k] + D[k][j]

위 코드는 플로이드 워셜 알고리즘을 나타냅니다.
알아보기 쉽게 아래와 같은 표를 만들어 줍니다.

표에서 나타나는 행렬을 D[i][j]라고 했을 때 그 값은 정점 i에서 j로 갈 때의 값입니다.
INF는 무한대라는 의미로 D[1][2]의 경우 정점1이 정점2와 바로 연결되어 있지 않기 때문에 INF로 저장해줍니다.

k의 값을 증가시켜 보겠습니다.
k가 1일 경우 정점 1을 경유한 이후 최솟값을 저장하게 됩니다.

표시된 부분이 변경된 부분입니다.
기존의 값 D[2][3]보다 D[2][1] + D[1][3]의 값이 더 작았기 때문에 D[2][1] + D[1][3]을 D[2][3]의 값을 수정합니다.

이러한 과정을 모든 정점 수만금 반복합니다.

이후 행렬 D에는 모든 정점에 대한 최단거리가 저장됩니다.

3. 불가능한 예시

표시된 정점들을 확인하면
1. 싸이클이 형성된다.
2. 형성된 싸이클의 가중치의 합이 음수이다.
인 것을 확인할 수 있습니다.
이러한 상황이 형성될경우 싸이클을 무한히 반복할 경우 가중치의 합이 끝없이 작아지기 때문에 최솟값을 찾을 수 없습니다.

4. 시간 복잡도

앞서 언급한 코드를 보면 알 수 있습니다.
살펴볼 그래프의 정점을 V라고 할 때 시간 복잡도는 O(V^3)입니다.
앞서 살펴본 다른 알고리즘들의 경우 시간복잡도에 edge가 관여합니다.
그렇기 때문에 edge가 많은 그래프의 경우 플로이드-워셜 알고리즘이한 것을 알 수 있습니다.
종합적으로
1. 여러 정점의 최단 거리를 찾아야 한다.
2. 그래프의 edge가 다수 존재한다.
이러한 경우에 플로이드-워셜 알고리즘을 사용하면 됩니다.