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

시간 복잡도

$O(N^3)$

공간 복잡도

$O(N^2)$

---

        // 플로이드-워셜 알고리즘 실행
        for (int k = 1; k <= N; k++) {
            for (int i = 1; i <= N; i++) {
                for (int j = 1; j <= N; j++) {
                	if(i == j) continue;
                
                    if(arr[i][j] > arr[i][k] + arr[k][j]) {
                    	arr[i][j] = arr[i][k] + arr[k][j];
                    }
                }
            }
        }

• 모든 정점을 경유점으로 고려: 각 정점 k에 대해, 모든 정점 쌍 (i, j)의 거리를 검토하고,
  i에서 k를 거쳐 j로 가는 경로가 기존의 i에서 j로 가는 경로보다 짧은지 비교합니다. 만약 더 짧다면, 해당 경로의 거리로 업데이트합니다.

                if(arr[i][j] > arr[i][k] + arr[k][j]) {
                	arr[i][j] = arr[i][k] + arr[k][j];
                }

arr[i][j]의 기존 경로가 k를 거쳐서 이동할 때의 거리보다 짧을 경우 갱신한다.

i -> k -> j로 이동하니까 중간에 k를 다리로 이용한다고 생각

[i][k] -> [k][j] 각 중간에 k가 들어간다.