[SWIFT 알고리즘] 플로이드 최단거리 구하기

Floyd 알고리즘은 DP를 이용한 최단거리를 귀하는 알고리즘이다. 모든 정점에서 모든 정점으로의 최단거리를 구할때 사용한다. 모든 정점에서 모든 정점이기 때문에, 2차원배열을 사용한다. 한점에서 모든 정점으로의 최단거리를 구하는 다익스트라 알고리즘을 N번 돌리는 결과과 동일하지만, Floyd 알고리즘이 N*다익스트라 보다 시간복잡도가 더 낫다. 

사실 모든 최단거리 문제는 최적해의 원칙을 따른다. 만약 Vk가 Vi에서 Vj로 가는 최적의 길의 가운데 있는 node라면, Vi - Vk 와 Vk - Vj 도 역시 최적의 길이다.

Floyd 알고리즘의 DP가 진행되는 방식은 다음과 같다. 2가지 케이스가 존재한다.

1. Dk[from, to] = Dk-1[from, to] : 한번에 가는것이 더 빠른가

2. Dk[from, to] = Dk-1[from, k] + Dk-1[k, to] : k를 거쳐서 가는것이 더 빠른가

이러한 상황이 가능한 이유는 최단거리 문제는 최적해의 원칙을 따르기 때문이다. 따라서 이 2개의 값중에 더 최적값을 찾으면 되는 것이다. 그렇다면, Dk[from, to] = min(Dk-1[from, to], Dk-1[from, k] + Dk-1[k, to]) 가 DP적 접근이다.

노드가 1부터 시작한다면, 1 ~ k까지 수행하면된다. 반면 노드가 0부터 시작한다면, 0 ~ k-1까지 진행하면된다.

그래서 Floyd 최단거리 문제의 key point는 거쳐가는 정점을 기준을 최단거리를 구하는 것이다.

Floyd 알고리즘 시간복잡도

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

그래프를 나타내는 인접행렬이 이렇게 존재한다면

먼저 0번노드를 거쳐가는 곳을 찾는다면 갱신할 수 있는 곳은 지금 형광펜을 칠한 곳이다. 왜냐하면 0번에서 직접 갈 수 있는 matrix[0][], matrix[][0]을 제외하고, 자기 자신을 가르키는 곳을 제외하면 이렇게 나온다.

우리는 여기서 이제 비교를 하는 것이다. 바로 가는 것과 1을 거쳐서 가는 것과 비교를 한다. matrix[1][2]는 현재 9이다. 그렇다면 matrix[1][0] + matrix[0][2] 과 matrix[1][2]를 비교하면 된다. matrix[1][0]이 7이고, matrix[0][2]가 무한대임으로, matrix[1][2]가 더 작기에 그대로 있게된다. 이렇게 진행하게되면, 다음단계의 매트릭스가 만들어진다.

이제는 다음 위의 메트릭스를 기준으로 다음 메트릭스를 만들어야한다. 이번에는 노드 1을 거쳐서 가는 것을 만들어야한다. 그렇다면 matrix[0][2]를 찾는다고 한다면, 원래 matrix[0][2]는 무한이고, 노드 1을 거쳐서 가는 방식은 matrix[0][1]+matrix[1][2]이다. matrix[0][1] == 5, matrix[1][2] == 9이다 따라서 14 < INF 이므로, matrix[0][2]의 값을 INF -> 14로 변경해주면 된다. 

이런 방식으로 이어간다면 노드1을 거쳐서 가는 최단거리는 이렇게 된다. 이러한 방식으로 다른것들을 계속 이어나가면된다.

코드

import Cocoa

let num = 4;
let INF = 1000000

var graph : [[Int]] = [
    [0, 5, INF, 8],
    [7, 0, 9, INF],
    [2, INF, 0, 4],
    [INF, INF, 3, 0]
]

func floydSPT(){
    //결과 그래프 초기화
    var result = [[Int]](repeating: [0,0,0,0], count: num)
    for i in 0..<graph.count{
        for j in 0..<graph[i].count{
            result[i][j] = graph[i][j]
        }
    }
//    mid = 거쳐가는 vertex, from은 출발, to는 도착
    for mid in 0..<num{
        for from in 0..<num{
            for to in 0..<num{
                if (result[from][mid] + result[mid][to]) < result[from][to]
                {
                    result[from][to] = result[from][mid]+result[mid][to]
                }
            }
        }
    }
    //결과 출력
    for i in 0..<num{
        for j in 0..<num{
            print(result[i][j], terminator: " ")
        }
        print("\n")
    }
}

floydSPT()