지난 포스팅에서는 다익스트라 알고리즘에 대해 작성했었다. 다익스트라의 경우 한 지점에서 다른 특정 지점까지의 최단 경로를 구하는 알고리즘이다. 그러나 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야하는 경우에는 어떻게 해야할까?
바로 플로이드 워셜 알고리즘을 사용하면 된다. 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구하는 알고리즘이다. 아래 정리한 내용을 살펴보면 이해하는데 도움이 될 것이다.
N
개라고 할 때, N
번 만큼의 단계를 반복하며 '점화식에 맞게' 2차원 리스트를 갱신하기 때문에 DP라고 볼 수 있다.<--> 다익스트라는 그리디 알고리즘에 속한다고 볼 수 있다.플로이드 워셜 알고리즘의 점화식은 아래와 같다.
[step 0] 그래프의 노드와 간선에 따라 최단 거리 테이블을 갱신한다.
[step 1] 1번 노드를 거쳐 가는 경우를 고려하여 테이블을 갱신한다.
[step 2] 2번 노드를 거쳐 가는 경우를 고려하여 테이블을 갱신한다.
[step ~] 3번, 4번, ... 노드를 거쳐 가는 경우를 고려하여 테이블을 갱신한다.