플로이드 와샬

플로이드 와샬(Floyd Warshall)은 간선에 비용이 있는 그래프에서

모든 점에서 모든 점까지의 최단거리를 구할 수 있는 모든 쌍 최단거리 알고리즘입니다.

이 알고리즘은 반복적 동적 계획법과 슬라이딩 윈도우 기법을 사용하며

dist[i][j]는 i 정점에서 j 정점까지의 최단거리를 뜻할 때

거치는 점(k) - 출발점(i) - 도착점(j) 순의 3중 포문을 이용하여

매 k마다 모든 i, j값을 순회하여 k 정점을 추가적으로 경유하였을 때의 값이 더 작은 경우(dist[i][j] > dist[i][k] + dist[k][j])

dist[i][j]값을 갱신하여 최단거리를 저장합니다.

3중 포문의 형태를 띄고 있으므로 시간복잡도는 정점 개수가 V일 때 O(V^3)이 되며

코드가 매우 간결하므로 V가 크지 않을 경우의 최단거리를 구할 때에도 유용하게 쓸 수 있는 알고리즘입니다.

기본 문제

11404번: 플로이드

1956번: 운동

2610번: 회의준비