Floyd Wharshall 플로이드 와샬

목표

- 하나의 정점에서가 아닌 모든 정점에서 모든 정점으로 가는 최단 경로를 구하고 싶을 때 사용한다.
- 거쳐가는 정점을 기준으로 알고리즘을 수행한다. 
- 삼중 for문을 사용해 구현하므로 O(n^3)의 시간 복잡도를 갖는다.

 

---

 

플로이드 와샬 알고리즘 ?

플로이드 와샬 알고리즘은 한 정점에서 시작해 모든 정점을 탐색하는 최단 방법을 다룬 다익스트라나 다른 그래프 탐색 알고리즘과 달리
모든 정점에서 모든 정점의 최단 경로를 구하고 싶을 때 사용합니다.

핵심 아이디어는 A -> B 노드로 갈 때, 
A -> B 로 바로 가는 경우 와 A -> K -> B 로 어떤 노드 k를 거쳐가는  방법
을 비교해서 최소값을 구하자는 것입니다.

 

 

 

구현은 가중치 테이블을 이용합니다.

아직 연결이 되지 않은 노드는 ∞으로 두고 [from][to] 와 [from][k] + [k][to] 의 값을 비교해서 더 적은 값으로 갱신해줍니다.

 

구현

구현은 거쳐가는 노드를 가장 바깥 포문으로 두고 3중 포문을 사용해서

바로가는 방법과 거쳐가는 방법을 비교해 더 적은 값으로 바꿔줍니다.

 graph[from][to] = min(graph[from][to], graph[from][k] + graph[k][to] 

 

graph = [[Int]]()
// graph 설정

// FloyWarshall 알고리즘
func floydWarshall() {
  // 거쳐가는 노드
  for k in 0..<n {
    for from in 0..<n {
      for to in 0..<n {
        if from == to { continue }
        graph[from][to] = min(graph[from][k] + graph[k][to], graph[from][to])
      }
    }
  }
}