[Swift Algorithm] 플로이드 와샬

그래프 문제에서 자주 출제되는 문제유형중 하나에요

알고 있으면 정말 유용하게 사용 할 수 있다고 생각해요

 

그래프유형에서 

크루스칼 알고리즘과

플로이드 와샬이 대표적인 그리디 알고리즘이에요

 

크루스칼은 최소 간선을 싸이클 없이 더해가면서 최소 비용을 찾는 과정이라면

(한 정점에서 다른정점으로 가는 최단거리)

 

플로이드 와샬은 현재 노드의 최솟값을 지정할때 현재값과 다른 경로로 왓을때의 최솟값을 비교해서 넣어주는 방식이에요

(모든 정점에서 다른정점으로 가는 최단거리)

 

1에서 5까지가는경우는

1 - 2 - 3 - 5 -> 비용5

1 - 2 - 5 -> 비용 3

 

플로이드 와샬은 이런경우에 유용해요

사용하면 1에서 5까지의 비용은 3이라고 저장되는 방식이에요

 

    func 플로이드와샬() {
        for i in 0..<N {
            for j in 0..<N {
                for k in 0..<N {
                   node[j][k] = min(node[j][i] + node[i][k], node[j][k])
                }
            }
        }
    }

위는 핵심코드에요

 

[j][k]값과 [j][i] + [i][k] 중 작은값을 저장하는거죠

즉 현재값과 거쳐서오는 최솟값을 비교하는거에요

위의 그림에서 예시를들자면

[2][5]와 [2][3] + [3][5] 를 비교할 경우가 생기겠네요