플로이드 와샬

플로이드 와샬

• 그래프 문제에서 자주 출제되는 문제 유형.
• 그래프 유형에서 크루스칼과 플로이드 와샬이 대표적인 그리디 알고리즘
• 크루스칼 → 최소 간선을 싸이클 없이 더해가면서 최소 비용을 찾는과정 (한 정점에서 다른 정점으로 가는 최단거리)
• 플로이드 와샬 → 현재 노드의 최솟값을 지정할 때 현재 값과 다른 경로로 왔을 때의 최솟값을 비교해서 대입하는 방식 (모든 정점에서 다른 정점으로 가는 최단거리)

이런 그래프에서 1에서 5까지 가는 경우를 생각해보면

1. 1-2-3-5 : 5코스트
2. 1-2-5: 3코스트

플로이드 와샬은 이런 경우에 유용함!

코드 형태

func floydWarshall() {     
  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])             
      }     
    }   
  } 
}

이런 식으로 플로이드 와샬은 시작 : 1...n 중간: 1... n 도착: 1...n 까지 n의 3제곱으로 모든 경우의 수를 탐색하는 것

핵심은 위와 같이 현재 값인 [j][k]값과 [j][i] + [i][k] 값 중 작은 값을 저장하는 것, 마치 DP 처럼!

여기서 [j][k]라는 뜻은 j 정점으로부터 k 정점 까지의 거리라는 뜻

참고: https://fomaios.tistory.com/entry/Algorithm-플로이드-와샬Floyd-Warshall-이란

Uploaded by

N2T