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

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

---

플로이드-워셜 (이하 플로이드)알고리즘은 그래프에서 최단거리를 찾을 때 사용하는 알고리즘이다. 

그래프에서의 최단거리를 찾을 때 가장 대표적인 알고리즘은 다익스트라(링크) 알고리즘이다.

 

다익스트라 알고리즘은 특정 시작지점에서 모든 노드까지의 최소거리를 알고 싶을 때 사용했다.

즉 다익스트라를 이용하면 하나의 시작노드에서의 정보밖에 얻을 수 없다.

 

그렇다면 모든 노드를 시작지점으로 해서 각 노드까지의 최소거리를 모두 알고 싶다면 어떻게 할까?

가장 먼저 떠오르는 생각은 다익스트라 알고리즘을 V(정점의 개수)만큼 반복시키는 것이다.

다익스트라 알고리즘 설명에서 다익스트라의 시간복잡도는 O(E*logV)라고 했다. 이는 우선순위 큐를 바이너리 힙으로 구현했을 때의 이야기인데, 사실 피보나치 힙을 이용하면 더빠르게 만들 수 있다.(여기서는 설명하지 않는다.)

피보나치 힙을 이용하여 다익스트라 알고리즘을 구현하면 시간복잡도는 O(VlogV + E)가 된다. 

 

그렇다면 일단 다익스트라의 시간복잡도는 가장 빠를 수 있는 O(VlogV+E)로 생각한다.

또한 앞서 이야기 했듯 모든 노드를 시작지점으로 하는 최소거리의 정보를 알고 싶을 땐 다익스트라를 V번 돌리면 된다고 했다.

이 아이디어로 수행한다면 다익스트라를 이용하여 모든 정점을 시작노드로 하는 최소거리를 구하는 알고리즘의 시간복잡도는 O(V*(VlogV+E))가 될것이다. 가장 최악의 경우를 생각한다면 밀집한 그래프(dense graph - 모든 정점이 모든 정점으로 갈 수 있는 상태)에서는 E=V^2이므로 최종 시간 복잡도는 O(V^3)이 될것이다.

 

서론이 길었다. 어쨌든 다익스트라를 이용해 모든 정점을 시작으로해서 모든 정점까지의 최단거리를 구하는 알고리즘의 시간복잡도는 O(V^3)이다.

 

플로이드 알고리즘또한 시간복잡도는 O(V^3)이다.

그러면 이 알고리즘을 왜 공부할 필요가 있을까? 다익스트라만 알면 되는거 아닌가?

아니다. 플로이드 알고리즘은 다익스트라와 달리 간선(엣지)의 가중치가 음수여도 가능하다. 

 

설명

---

플로이드 알고리즘은 기본적으로 V*V의 이차원 배열 V번 사용해 진행된다.

다음과 같은 그래프가 있다.

이 그래프를 이차원 배열로 표현하면 아래와 같이 표현할 수 있다.

위의 이차원 배열을 시작으로 N(1<=N<=V)번 반복한다.

N=1일때는 1번노드를 거쳐 갈때 최소거리를 구하는 것이다.  또한 행과 열이 같은 칸(자신부터 자신)과 행이 N이거나 열이 N인 칸은 연산을 하지 않는다 (N=1일때는 1번노드를 거쳐갈때를 기준으로 연산하는데, 행또는 열이 N이면 이미 노드 N이 걸쳐있기 때문)

이해를 돕기위해 한가지 예시를 들자면,

 

 

 

N=1일때, 왼쪽 표에서 현재 (2,3)의 셀에 접근해있다고 가정하자.

1번노드를 거쳐서 2번 노드→3번 노드로 가기 위해서는 

2→1 과 1→3을 (녹색 칸들)거치면 될것이다. 

현재 노란색칸의 값보다 녹색칸들 값의 합이 더 작다면 노란색칸을 두 녹색칸의 합으로 업데이트 시키면 되는 것이다.

 

 

 

 

 

N=1일때 X인 칸(행=열)과 행 또는 열이 N인칸을 제외하고 위와같은 연산을 진행하면 다음과 같다.

위 과정을 계속 진행하다보면 N이 2와 3일때는 다음과 같다.

변화가 없다. 2번노드를 거쳐도 업데이트될 필요가 없기 때문이다.

그러나 N=3일때는 업데이트가 발생한다.

다시 예시를 들자면 다음과 같다.

 

 

셀 (1,4) (1번 노드 → 4번 노드)에서 3번노드를 거쳐서 갈 경우는

1→3과 3→4를 거치면 된다 (녹색 칸)

현재 칸은 무한대로 설정되어있고 녹색칸들의 합은 13이다.

무한대보다는 13이 작으므로 해당칸을 13으로 업데이트 시킨다.

 

 

 

 

 

 

마찬가지로 행=열인 칸과 행 또는 열이 3인 칸을 제외한 모든칸의 연산을 마치면 다음과 같다.

마찬가지로 N이 4,5,6일때 모든 과정은 다음과 같다.

N이 6일때까지 모든 연산을 마쳤다면(N=V) 그때의 배열이 모든 정점으로부터 모든 정점까지의 최소거리 정보를 담고있는 배열이 된다.

값이 무한대라면 해당 루트는 없는 것이다.

 

구현

---

구현은 간단하다. 그저 배열을 순회하며 값이 크고작은지만 판단하면 되기 때문이다.

for(int N=1;N<=V;N++){
        for(int y=1;y<=V;y++){
            for(int x=1;x<=V;x++){
                if(y==x || y==N || x==N) continue;
                if(matrix[y][x]>matrix[N][x]+matrix[y][N]){
                    matrix[y][x] = matrix[N][x]+matrix[y][N];
                }
            }
        }
    }

3충 for문을 V만큼 돌기때문에 시간복잡도는 O(V^3)이다.

 

우선순위 큐를 사용하는 다익스트라와 비교하여 비교적 단순한 연산과 구현때문에 편리하고, 가중치가 음수일때도 사용할 수 있다.

 

이 코드를 그대로 가져다 쓰면 백준 11404(플로이드)를 해결할 수 있다!