정의

플로이드-워셜은 "모든 점에서 모든 점으로 가는 최단 거리"를 한 번에 구하는 알고리즘입니다. 중간 경유지를 하나씩 늘려가며 더 짧은 경로가 있는지 확인합니다.

핵심 특성

• ✓모든 쌍 최단 경로: 한 번의 실행으로 모든 (i, j) 쌍의 최단 거리를 계산합니다.
• ✓동적 프로그래밍: dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) 점화식을 사용합니다.
• ✓음수 가중치 허용: 음수 사이클이 없다면 음수 간선도 처리 가능합니다.

시간 복잡도