[9급 국가직 알고리즘 2024년 13번]

○ 모든 쌍 최단 거리(all pairs shortest path)를 구하는 알고리즘이다.

○ 음수의 가중치를 가진 간선(edge)이 있어도 수행될 수 있다.

○ 동적 계획법(dynamic programming)의 원리를 이용한다.

○ 시간복잡도는 $O(n^3)$이다. (단, $n$은 정점의 수이다)