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

플로이드 와샬 알고리즘

 모든 정점에서 모든 정점으로 가는 최단 거리를 구하는 문제들이 있다. 이 경우 플로이드 와샬 알고리즘을 사용하면 쉽게 모든 정점의 최단 거리를 구할 수 있다. 플로이드 와샬을 기본적으로 DP를 기반으로 진행된다.

 

 

플로이드 와샬 알고리즘의 주요 아이디어는 거쳐가는 정점을 기준으로 최단 거리를 구하는 것이다.

 

위 와 같은 그래프가 존재한다고 가정하자.이 때 각 정점에서 다른 정점으로 가는 비용을 이차원 배열로 정리하면 아래와 같다.

 해당 테이블이 의미하는 바는 '현재까지의 최단 거리'이다. 해당 테이블을 통해 지나치는 정점으로 다른 정점으로 가는 테이블을 그릴 것이다.

 

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

 노드 1을 거쳐가는 경우는 노드 2와 노드 3이다. 이를 테이블로 나타내면 아래와 같다.

노란 부분이 노드 1을 거쳐 도착할 수 있는 부분이다. 해당 부분을 '현재까지의 최단 거리'와 '노드 1까지의 거리 + 노드 1에서 해당 부분으로 가는 거리'를 비교하여 작은 거리를 입력하면 해당 노드로 가는 현재까지의 최단 거리를 새로 구할 수 있다.

 

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

 노드 2를 거쳐가는 경우도 위와 같이 풀이하면 아래와 같은 테이블이 나온다.

 

위와 같이 노드 3과 노드 4도 반복을 하게 되면 최종적으로 아래와 같은 테이블을 얻을 수 있다 .해당 테이블은 각 정점으로 가는 최단 거리를 나타낸다.

 

 

Reference

- https://m.blog.naver.com/ndb796/221234427842