플로이드(Floyd) 알고리즘

• 0. Intro

• 1. 플로이드(Floyd) 알고리즘

• 2. How?

• 3. 코드

• 4. 복잡도

0. Intro

자료구조 수업 때 그래프 부분에서 다익스트라 알고리즘에 대해 배운 적이 있습니다.

다익스트라 알고리즘 경우에는 한 시작점에서 다른 정점까지의 최단 거리를 구하는 알고리즘이었습니다.

 

이번에는 그래프에서 모든 정점 쌍 사이의 최단 경로를 찾는 플로이드 알고리즘에 대해 소개해보겠습니다.

개인적으로 다익스트라 알고리즘보다 훨씬 이해하기는 쉬운 알고리즘 같습니다.

 

단, 플로이드 알고리즘은 음수 가중치가 없는 무조건 양수의 그래프에서만 유효한다는 것을 주의해야 합니다.

 

1. 플로이드(Floyd) 알고리즘

플로이드 알고리즘은 동적 계획법(Dynamic Programming) 기법을 사용합니다. 이를 위해서는, 그래프의 인접 행렬(adjacency matrix)을 이용하여 모든 정점 쌍 사이의 최단 경로를 저장하는 행렬을 만듭니다. 이때, 행렬의 원소값을 갱신하면서 최단 경로를 구해나갑니다.

 

이렇게 말로 설명하는 거 보다 예시를 들면 이해가 쉽게 될 것입니다.

 

이 그림을 이해하면 플로이드 알고리즘을 이해했다고 볼 수 있습니다.

 

이 그래프를 보면 A에서 B로 한 번에 가면 10의 비용이 발생합니다.

하지만 A->C->B로 거치게 되면 2+4 = 6의 비용으로 더 적은 비용으로 갈 수 있습니다.

 

플로이드 알고리즘은 이런 모든 경우를 하나 하나씩 체크해서 더 적은 비용일 경우에 갱신하는 방식으로 되어 있습니다.

 

2. How?

자 이제 우린 모든 정점의 쌍들의 최단거리를 구할 수 있습니다.

 

가장 간단한 구현 방법은 2차원 매트릭스로 구현하는 것 입니다.

 

A, B, C 3개의 정점이 있다고 가정해 보겠습니다.

정점	A	B	C
A	0	10	2
B	10	0	5
C	2	4	0

 

1. A-A로 가는 비용은 제자리 걸음이기 때문에 비용을 0으로 설정합니다.

 

2. 먼저 초기 설정은 모든 cell를 굉장히 큰 값(INF)으로 둡니다. (최소 비용을 구하는 것이기 때문에 0으로 설정하면 계속 0으로 저장된다.)

 

3. 간선이 있는 경우, 예를 들어 A->B와 B->A의 경우 모두 10의 비용의 간선이 있기 때문에 해당 값을 INF가 저장된 값에 덮어 저장합니다. 

 

4. 그 후 다음 다른 정점을 경유하는 경우와 본래 비용을 비교해줍니다.

cost[i][j] = MIN(cost[i][j], cost[i][k] + cost[k][j]);

// i->j경우와 i->k->j의 경우의 비용을 비교하여 최솟값을 저장

 

3. 코드

for(i = 1; i<=n; i++)
        for(j = 1; j<=n; j++)
            for(k = 1; k<=n; k++)
                cost[j][k] = MIN(cost[j][k], cost[j][i] + cost[i][k]);

 

해당 코드를 실행하고, 출력하면 정점 쌍 사이의 최소비용이 갱신되어 있습니다.

 

cost[i][j] : i에서 j로 가기 위한 최소 비용

 

4. 복잡도

해당 알고리즘의 복잡도 계산도 간단합니다.

 

3번 코드 부분이 Basic operation이기 때문에 O(n^3)인 것을 확인할 수 있습니다.