플로이드 와샬(Floyd Warshall)

모든 정점에서 모든 정점으로의 최단 경로를 구하고 싶다면 플로이드 와샬 알고리즘을 사용한다.

"거쳐가는 정점을 기준으로 최단 거리를 구하는 것"

 

위의 그래프에서 각각의 정점이 다른 정점으로 가는 비용을 이차원 배열에 출력하면

 

 

이 테이블이 의미하는 것은 현재까지 계산된 최소 비용이다.
이러한 이차원 배열을 반복적으로 갱신하여 최종적으로 모든 최소 비용을 구해야 한다.
반복의 기준이 '거쳐가는 정점' 인 것이다.

1.  노드 1을 거쳐가는 경우
   
   

 

노드 1을 거쳐가는 경우는 위와 같이 6가지 공간만 갱신해준다.

 

즉, 예를 들어 2에서 3으로 가는 경우에는

2에서 3으로 가는 경우의 비용과  (2에서 1로 가는 경우) + (1에서 3으로 가는 경우)의 비용을 더한 값을 비교한다.

더 작은 값으로 교체한다.

 

 

2. 노드 2를 거쳐가는 경우

 

 

이 경우라면 위의 6칸만 비교해주면 된다.

 

 

똑같이 3, 4 노드에 대해 수행해주면 된다.

결과적으로 이렇게 된다.

 

플로이드 워셜 알고리즘은 동적 프로그래밍 기법을 사용한다.

 

 

삼중 포문을 이용해야된다는 점에서 시간복잡도는 O(N^3)이 된다.