[알고리즘] 최단거리 플로이드(Floyd) 알고리즘

플로이드(Floyd) 알고리즘

이번에는 조금 더 간단하게 최단거리를 구할 수 있는 알고리즘을 소개합니다.

다익스트라 알고리즘은 한 시작점에서 다른 정점까지의 최단 거리를 구하는데 반해 플로이드 알고리즘은 모든 정점 쌍에 대해서 둘 사이의 최단 거리를 구할 수 있습니다!

단, 플로이드 알고리즘은 음수 가중치가 없는 무조건 양수의 그래프에서 동작합니다.

경유점

어떤 정점 a와 b가 연결되어 있다고 할때 이 정점 사이에 c가 있다고 하지요. a와 b로 연결되어 있는 간선의 비용이 5라고 하구요.

하지만 a와 c의 비용은 2, b와 c의 비용은 2라고 한다면 a와 b로 가는데 c를 거쳐가는 것이 더 효율적이라는 것을 알 수 있습니다. a-c-b의 비용은 4이기 때문에 a-b의 비용 5보다 비용이 더 적습니다.

c와 같이 경로가 거쳐가는 정점이 경유점이라고 하지요.

플로이드 알고리즘은 두 정점 사이의 어떤 경유점이 존재한다면 경유점을 거쳐가는 것을 확인하면서 더 짧은 것을 선택하게 됩니다.

구현

아래와 같은 그래프가 있는데 모든 쌍의 최단거리는 어떻게 될까요?

1-4까지의 최단 거리?

0-3까지의 최단 거리?

...

이런 물음을 빈번하게 묻는 문제가 나올땐 다익스트라 알고리즘을 모든 정점에 대해서 구할 수 있지만 플로이드 알고리즘을 쓰면 보다 쉽고 또 빠르게 구할 수 있다는 장점이 있지요.

이제 본격적으로 구현해보도록 합시다.

그래프의 초기화

위의 그래프를 우선 배열로 구현해야합니다. 조건이 있는데, 초기에 직접적으로 연결되어 있지 않은 경로는 아주 큰 값으로 설정해야한다는 것이죠. 그리고 자기 자신까지의 비용은 0으로 만들어 줍니다.

정점	0	1	2	3	4
0	0	2	3	INF	INF
1	2	0	INF	INF	10
2	3	INF	0	1	4
3	INF	INF	1	0	2
4	INF	10	4	2	0

플로이드 알고리즘 적용

이제 플로이드 알고리즘만 적용시켜주면 되지요.

시작점은 i, 끝점을 j, 경유점을 k라고 했을때 구하는 식은 다음과 같습니다.

adj[i][j]=MIN(adj[i][j], adj[i][k]+adj[k][j])

이 경유점 k를 지나는 모든 i, j에 대해서 확인해주면 됩니다.

adj[i][j]와 adj[i][k]+adj[k][j] 중 항상 작은 값만을 갖게 되므로 직접적으로 연결이 되지 않는 간선은 INF로 처음에 초기화 한 이유를 아시겠어요?

만일 경유점 k가 0이라고 할때 adj[1][2] = MIN(adj[1][2], adj[1][0] + adj[0][2]) = MIN( INF, 5) = 5 가 됩니다. 결국 1-2까지의 경로는 5로 더 작은 값이 됨을 알 수 있죠.

그 후 경유점이 k=2가 되었다고 할때 adj[1][3] = MIN(adj[1][3], adj[1][2] + adj[2][3]) = MIN(INF, 6) = 6이 됩니다. 왜냐면 방금전 adj[1][2]를 구해냈기 때문이지요. 그래서 1-3까지의 비용은 6이 되는 것을 알 수 있습니다.

이렇게 모든 경유점을 확인하면서 비용이 작은 값만을 선택합니다.

이제 전체 코드를 보면서 결과를 확인해보세요.

#include <stdio.h>
#define MAX_V 10
#define MIN(a,b) a<b ? a:b
#define INF 987654321
int V,E;
int adj[MAX_V][MAX_V];
void initAdj() {
	int i, j;
	for (i = 0; i < V; i++)
		for (j = 0; j < V; j++) {
			adj[i][j] = INF;
			if (i == j)adj[i][j] = 0;
		}
}
void floyd() {
	int k,j,i;
	
	for (k = 0; k < V; k++)
		for (i = 0; i < V; i++)
			for (j = 0; j < V; j++)
				adj[i][j] = MIN(adj[i][j], adj[i][k] + adj[k][j]);
}
int main() {
	int i, j;
	printf("정점 개수:");
	scanf("%d", &V);
	printf("간선 개수:");
	scanf("%d", &E);

	initAdj();

	printf("정점 연결( 정점1 정점2 비용) \n");
	for (i = 0; i < E; i++) {
		int v1, v2, cost;
		scanf("%d %d %d", &v1, &v2, &cost);
		adj[v1][v2] = adj[v2][v1] = cost;
	}


	floyd();

	for (i = 0; i < V; i++) {
		for (j = 0; j < V; j++)
			printf("%d~%d까지의 최단거리:%d\n", i, j, adj[i][j]);
		printf("\n\n");
	}
}

경유점 k의 순서가 꼭 0부터 V까지 순차적일 필요는 없습니다. 경유점을 어느 순서로 해도 상관이 없다는 것이죠.

복잡도

위 코드의 시간복잡도는 O(V^3)이 되고 공간복잡도는 O(V^2)가 됩니다. 플로이드 알고리즘은 V가 작고 모든 정점의 최단 거리를 구할때 아주 유용하고 쉽게 구현할 수 있기 때문에 기억해둘만한 가치가 충분히 있습니다.