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

들어가며

Baekjoon 11403 문제를 접하게 되면서 플로이드 워셜에 대해 알게되었고 그에 대해 간단하게 공부해보려고 한다.

---

플로이드 워셜(Floyd-Warshall)이란?

• 모든 지점에서 다른 모든 지점까지의 최단 경로를 구하는 알고리즘. 즉 모든 노드간의 최단 경로를 구하는 알고리즘이다. 
• 시간 복잡도는  $ O\left ( V^{3} \right ) $ 이며, 다익스트라 알고리즘과 다르게 음의 가중치를 가지는 그래프에서도 사용할 수 있다.

거쳐가는 정점을 기준으로 한다

 

예시)

위와 같은 그래프가 존재한다고 생각합시다. 

이때 만나지 못하는 정점의 관계는 무한, 자기자신의 정점은 0으로 두고 각각 정점을 기준으로 표로 정리하게 되면.

	1	2	3	4
1	0	5	무한	8
2	7	0	9	무한
3	2	무한	0	4
4	무한	무한	3	0

현재까지 계산된 최소 비용은 이렇게 나타낼 수 있습니다 . 

 

그럼 이때 노드 순서대로 각각의 노드를 거쳐가게 된다면 위의 표에서 갱신이 이루어질 수 있는 곳을 봅시다. 

 

1번 노드를 거쳐간다면?

	1	2	3	4
1	0	5	무한	8
2	7	0
3	2		0
4	무한			0

이때 2 -> 3으로 가는 노드를 예시로 들면 기존에 있던 9와 2 -> 1, 1 -> 3으로 가는 경로를 비교하는 것이다. 그러면

9(기존)  vs 7 (2->1) + 무한(1->3) => 9가 가장 작은 최소비용이 되기에 9로 산정될 수 있는 것이다.

 

이런식으로 계산한다면

 

2 -> 4

무한(기존) vs 7(2->1) + 8(1->4) = 15

3 -> 2

무한(기존) vs 2(3->1) + 5(1->2) = 7

.

.

.

	1	2	3	4
1	0	5	무한	8
2	7	0	9	15
3	2	7	0	4
4	무한	무한	3	0

 로 1번 노드를 거쳤을때가 끝나는 것이다. 

 

이와 같이 플로이드 워셜은 의외로 간단하다. 코드로 구현하면 아래의 코드와 같이 3중 반복문을 통해 플로이드 워셜을 구현할 수 있게 된다. 

void FolydWarshall() {
  for(int i = 0; i < N ; i++) {
    for(int j = 0; j < N; j++) {
      for(int v = 0; v < N; v++) {
        if(fd[j][v] > fd[j][i] + fd[i][v]){
          fd[j][v] = fd[j][i] + fd[i][v];
        }
      }
    }
  }
}

 

 

이상 플로이드 워셜에 대해 기초적인 개념 부분에 대해 알아봤다. 다음 포스팅에는 문제에서의 활용에 대해 알아보려고 한다. 

 

공부자료

https://www.youtube.com/watch?v=9574GHxCbKc