Floyd-Warshall Floyd-Warshall은 모든 정점에 대해 모든 다른 정점에 대한 최단 경로를 다 구하는 것이다. 또한, 음수 가중치의 경우도 구할 수 있다. 알고리즘은 비교적 간단하다. 관련 문제 백준 11404번 플로이드 기본 개념 3중 for loop 사용 방향, 무방향 그래프 둘다 사용가능, 사이클이 생기면 안된다 음의 가중치 적용 가능 a->b로 가는 최단거리가 a->c->b보다 크면 그 값을 갱신한다 아래의 조건문이 핵심이다 if (arr[i][k] + arr[k][j] < arr[i][j]) { // k를 거쳐가는게 더 작으면 arr[i][j] = arr[i][k] + arr[k][j]; // arr[i][j] 값 갱신 } 시간 복잡도 O(n^3) floyd 구현 각 반복문의 ..