[Algorithm] 플로이드 와셜(Floyd-Warshall) 개념 뿌수기!!

1. What is Floyd Warshall?

 플로이드 와샬 알고리즘은 '모든' 정점 사이의 최단 경로를 구할 때 사용하는 알고리즘 입니다. 한 정점->인접한 다른 정점으로 갈 때 비용을 전부 2차원 배열에 저장합니다. 모든 정점을 포문으로 탐색하게 되는데 이때 특정 한 정점일 때 해당 정점을 거쳐서 갈 수 있는 경로가 원래 2차원 배열에 저장된 경로의 비용보다 낮다면 2차원 배열의 cost를 갱신합니다. 

2. Floyd Warshall's algorithm

인접 정점 간 갈 수 있는 비용을 2차원 배열 visited에 저장했다고 가정한다면 점화식은

visited[v][w] = min(visited[v][w], visited[v][k] + visited[k][w])입니다. 

v : 시작 정점

w : 도착 정점

k : k 정점을 

// 원래 시작 정점 -> 도착 정점 vs 시작정점 -> k정점 -> 도착 정점. 이 중 무엇이 큰지를 파악해 나갑니다.

 

for k in 0..<vCnt {
    for v in 0..<vCnt {
        for w in 0..<vCnt {
            if visited[v][k] == Int.max || visited[k][w] == Int.max {
                continue
            } // 무한대 + 무한대 의 경우 컴파일 에러가 발생함으로 패스!
            visited[v][w] = min(visited[v][w], visited[v][k]+visited[k][w])
        }
    }
}

2. Floyd Warshall's Exercise

C로 배우는 쉬운 자료구조. 그림1

이런 그래프가 있습니다. 5개의 정점(A,B,C,D,E)이 있습니다. 정점과 정점을 연결하는 간선 이외의 값을 무한대 INF로 표시한다면 2차원 배열에 '방향'이 있는 정점 간 cost를 저장할 수 있습니다.

 

2차원 배열 이름 : visited[][]

visited[0], visited[1], visited[2],visited[3],visited[4] 는 시작 정점을 의미합니다.

visited[0]일 때 (시작 정점 = A) A정점에서 갈 수 있는 인접 정점은 B, C가 있습니다. 2차원 배열에서 비용을 찾기 위해선 아래와 같이 표현합니다.

 

visited[0][1] == 10 (A -> B cost)

visited[0][2] == 5 ( A -> C cost)

 

 그래서 겉 포문의 경우 시작 정점이 되겠고 안 포문의 경우 인접 정점 중 INF가 아닌 경우에 갈 수 있는 경우입니다. 즉 2차원 배열을 쓰면 한 정점에서 다른 정점으로 갈 때 비용을 2차원 배열에서 꺼낼 수 있습니다. 위에서 점화식의 표현에선 v가 시작정점. w가 시작정점에 해당됩니다.

 

그러나 Floyd Warshall 알고리즘은 v, w 뿐 아니라 k 라는 변수도 사용합니다.

시작 -> 도착 정점으로 가는 정점이 있는데 시작 -> 도착 정점 사이에 k 정점을 거쳐서 ( v -> k. k-> w)갈 수 있는 w 정점이 있다면 이 정점이 원래 visited 배열에 저장되었던 cost보다 작은지를 비교해 나가는 알고리즘 입니다. 이때 k는 A, B, C, D, E 모든 정점을 순환 탐색합니다.

 

 A정점부터 E 정점까지. 순차적으로 정점을 탐색하기 위해 맨 처음 A 정점을 탐색할 때 초기 탐색 시 k == A가 됩니다. ( "A를 거쳐 갈 수 있는 시작 -> 도착 정점이 존재 하는가?", " 그렇다면 기존에 기록 되었던 cost 보다 작은가?") 

 

그림 1에서 A를 지나 갈 수 있는 인접 정점은

E -> A -> B ( visited[E][B] = min(visited[E][B], visited[E][A] + visited[A][B])  

E ->  A -> C ( visited[E][C] = min(visited[E][C], visited[E][C] + visited[A][C])  

두 경우가 있습니다.

 

 이때 E -> B를 가는 경로가 작은지 E -> A(K에 해당됨) -> B 로 A를 거쳐 가는 경로가 비용이 작은지를 체크해서 더 작은 비용을 visited 배열에 갱신합니다. K는 A부터 E까지 모든 정점을 순차적으로 된다고 했습니다. 이때 특징은 이전에 갱신된 visited를 기준으로 새로운 K가 됬을 때 K를 거쳐 갈 수 있는 인접 정점이 있는지를 파악하는 것입니다. 물론 초기 visited[E][B]의 경우 INF입니다. K가 A 에서 B ->  C ...가 됬을 때는 특정 구간에서 비용이 점차 단축됨을 구해갈 수 있습니다.

 

 플로이드 워셜 알고리즘은 결국 for 문 3개를 사용해 O(V^3) 시간 복잡도를 갖게 됩니다.

 

 한가지 궁금한 점이 있었습니다. 우선순위 큐를 활용한 다익스트라를 사용해 모든 정점일 때를 시작점으로 최단 경로를 구하는 경우와 플로이드 알고리즘을 사용하는 경우 둘 중 어느것이 더 효율적인지 궁금했습니다. 물론 각각의 장 단점이 있습니다. 단톡방에 질문했는데,, 다익스트라의 경우 시간복잡도 O(VElogV) 이고 플로이드의 경우 O(V^3)이 됩니다. 그래프의 E는 최악의 경우에 V^2에 비례하지만 문제 조건에서 E가 V^2보다 작은 경우엔 다익스트라가 플로이드보다 유리하다고 합니다. ( Swift Algorithm Club :)