플로이드 와샬 (Floyd-Warshall) 알고리즘

이번에는 플로이드 와샬 알고리즘에 대해서 공부를 해보았다.

 

지난번 다익스트라 알고리즘에 이어서 최단거리와 관련된  알고리즘이다.

 

다익스트라는 하나의 정점에서 출발했을 때, 다른 모든 정점으로의 최단 경로를 구하는 알고리즘이었다면,

 

플로이드 와샬은 '모든 정점'에서 '모든 정점'으로의 최단 경로를 구해야할때, 플로이드 와샬을 사용해야 한다.

플로이드 와샬 알고리즘의 핵심 아이디어는 '거쳐가는 정점'을 기준으로 최단거리를 구하는 것이라고 보면 된다.

예시

1 , 2,  3,  4의 총 4개의 노드를 가진 그래프가 있다. 

이를 바탕으로  플로이드 와샬을 그려보면

플로이드 와샬

초기 그래프에 대한 표를 작성할 수 있고, 그 다음을 차례대로 노드1만 거치는 경우 부터 노드4만 거치는 경우를 따져가면서 값을 업데이트하면 된다. 그럼 오른쪽 아래와 같은 결과가 만들어진다.

 

python 소스코드는 3중for문이 특징이었다. 

       for k in ~ : k는 거쳐가는 노드

         for i in ~ : i는 출발 노드

           for j in ~ : j는 도착 노드

그래프를 초기화한 후 3중포문을 이용해서 생각보다 어렵지않게 플로이드 와샬을 구현할 수 있어서 여러 문제에도 적용해 보아야겠다. 시간복잡도는 보다시피 3중for문을 이용하니까 O(n^3)이 걸리게 된다. 간선의 수가 많으면 다익스트라보다 빠를 수는 있지만, 시작점으로부터 각 정점까지의 거리만 구해도 될때는 보통 다익스트라가 훨씬 빠르다.

음의 가중치 간선이 있으면 (음의 싸이클은 x) 다익스트라는 이용할 수 없지만 플로이드 와샬 알고리즘은 사용할 수 있다.

 

코딩테스트 문제에서는 간선의 가중치를 보고, 주어진 시간내에 되는지, 몇가지만 판단한 후에 다익스트라인지 플로이드 와샬인지 선택해서 접근하면 될 것 같다.

 

공부를 하고 글로 남기기는 것은 생각보다 쉽지 않다.....