플로이드 와샬 알고리즘(Floyd Warshall Algorithm)

 

플로이드 와샬 알고리즘이란?

'모든 정점'에서 '모든 정점'으로의 최단 경로를 구하는 알고리즘

 

 

다익스트라 알고리즘과의 차이점

다익스트라는 하나의 정점에서 다른 모든 정점까지의 최단 경로를 구하는 알고리즘으로 가장 적은 비용을 하나씩 선택한다. 하지만 플로이드 와샬 알고리즘은 기본적으로 '거쳐가는 모든 정점'을 기준으로 알고리즘을 수행한다.

 

 

알고리즘

 

위와 같은 그래프가 존재한다고 할 때, D는 각각의 정점이 다른 정점으로 가는 비용을 이차원 형태로 저장해놓은 것이다.

D(1)

처음에는 위와 같은 상태이다. 

이때 무한대는 이동하는 경로가 없다는 뜻이고 자신 자신의 비용은 0이다.

 

 

D[x][y] = x에서 y로 가는 최소 비용을 의미한다.

 

 

거쳐가는 정점을 K라고 하자.

X에서 Y로 가는 최소 비용과 X에서 노드 K로 가는 비용 + 노드 K에서 Y로 가는 비용을 비교했을 때,

후자가 더 작다면 최소 비용을 갱신해주면 된다.

 

 

1부터 5까지 각 노드를 거쳐가는 정점으로 두고 최소 비용을 갱신하는 과정은 다음과 같다.

 

D(2) = 2번 노드를 거쳐갈 때

D(3) = 3번 노드를 거쳐갈 때

 

D(4) = 4번 노드를 거쳐갈 때

 

모든 정점에서 모든 정점으로의 최단 경로

 

 

구현

 

 

 

 

나동빈님의 블로그를 참고하여 정리한 글입니다.

24. 플로이드 와샬(Floyd Warshall) 알고리즘