[Algorithm] Floyd-Warshall 플로이드-워셜

Floyd-Warshall

3중 for문 사용 -> N^3

N=1000 인 경우, 10억

결론: N이 작을수록 유리하다

 

각 점을 시작점으로 정하여 다익스트라의 최단 경로 알고리즘을 수행

1 -> 2 3 4 5 ..... N

2 -> 1 3 4 5 ..... N

정점 간의 최단경로 계산

 

시간 복잡도는 인접 행렬을 사용하면  O(n^3)이다. 단, n은 정점의 수

 

warshall은 그래프에서 모든 쌍의 경로 존재 여부(transitive-closure)를 찾아내는 동적 계획 알고리즘을 제안했고,

floyd는 이를 변형하여 모든 쌍 최단 경로를 찾는 알고리즘을 고안

D[i][j] = 정점 i에서 j로의 최소 비용
for k in 1->n // 경유지
  for i in 1->n (단, i!= k) // 출발지
    for j in 1-> n (단 j!=k, j!=i) // 도착지
      D[i][j] = min(D[i][k] + D[k][j], D[i][j])