플로이드 와샬(Floyd Warshall) 알고리즘

플로이드 와샬 알고리즘

모든 정점에서 모든 정점으로의 최단 경로를 구하는 알고리즘

각 경로에서 새로운 중간 노드로 사용할 수 있는 노드를 선택하고, 더 짧은 길이를 선택하여 줄이는 과정을 반복



시간 복잡도 

(최선 = 최악 = 평균)
O(V^3)

점화식

distance[i,j] = min(distance[i,j], distance[i,k] + distance[k,j])

 

코드

for(int k = 0; k < 4; k++)  // k 는 거쳐가는 정점
  for(int i = 0; i < 4; i++)  // i 는 행 (출발 정점)
    for(int j = 0; j < 4; j++)  // j 는 열 (도착 정점)
      if (a[i][k] + a[k][j] < a[i][j])  
        a[i][j] = a[i][k] a[k][j];