[Algorithm] 플로이드 워셜 알고리즘

다익스트라 알고리즘을 공부하다보면 나오게 되는 플로이드-워셜 알고리즘! 정말 이 알고리즘을 볼 때마다 감탄이 나오는 것 같다.

[Algorithm] 다익스트라 알고리즘

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

그래프에서 가능한 모든 정점 쌍에 대해 최단 거리를 구하는 알고리즘이다. 시간복잡도는 O(V^3)이지만 모든 노드 쌍에 대해 최단 거리를 구할 수 있다. 특히 다익스트라 알고리즘은 음의 가중치를 가지는 그래프에서 쓸 수 없는데, 플로이드-워셜은 쓸 수 있다.

🔥 Swift 구현

사실 이 알고리즘은 구현은 너무~나도 쉽다. 아래는 C언어로 구현된 코드인데, 그냥 한눈에 보이고, 이해가 될 정도로 간단하다.

void Floyd_Warshall() {
  for(m=1; m<=N; m++)
    for(s=1; s<=N; s++)
      for(e=1; e<=N; e++)
        if (d[s][e] > d[s][m] + d[m][e])
            d[s][e] = d[s][m] + d[m][e];
}

스위프트로 구현해보자면... 아래와 같다. 주의할 점은 중간 정점인 m이 반복문의 맨 위에 있고, 만약 Int.max로 연결되지 않는 간선을 표현한다고 한다면 연산할 때 오버플로우에 주의해야 한다는 점이다.

func floydWarshall(_ graph: [[Int]]) -> [[Int]] {
    var d = graph
    let n = graph.count

    for m in 0..<n {
        for s in 0..<n {
            for e in 0..<n {
                if d[s][m] != INF && d[m][e] != INF {
                    d[s][e] = min(d[s][e], d[s][m] + d[m][e])
                }
            }
        }
    }
    
    return d
}

💾 입력과 결과

아래와 같은 그래프를 넣으면 모든 모든 정점 쌍에 대해 최단 거리가 나오게 된다.

let INF = Int.max / 2  // 연결되지 않은 경우 무한대로 설정

let graph: [[Int]] = [
    [0, 7, 9, INF, INF, 14],
    [7, 0, 10, 15, INF, INF],
    [9, 10, 0, 11, INF, 2],
    [INF, 15, 11, 0, 6, INF],
    [INF, INF, INF, 6, 0, 9],
    [14, INF, 2, INF, 9, 0]
]

print(floydWarshall(graph).forEach { print($0) })

//  [0, 7, 9, 20, 20, 11]
//  [7, 0, 10, 15, 21, 12]
//  [9, 10, 0, 11, 11, 2]
//  [20, 15, 11, 0, 6, 13]
//  [20, 21, 11, 6, 0, 9]
//  [11, 12, 2, 13, 9, 0]