[알고리즘] 플로이드 워셜 최단거리 알고리즘

다익스트라, 벨만포드, 플로이드 워셜 ... 다 최단거리를 구하는 대표적인 알고리즘이다.

 

하지만 '최단거리'를 구한다는 공통적인 목표가 있지만, 각자 서로 다른 특징이 있기에 여러 알고리즘이 나눈다.

 

1. 다익스트라 

   장점 : 양의 간선이 존재할때 빠르게 최단거리를 구할 수 있다.

   단점 : 음의 간선이 존재할때는 최단거리를 보장할 수 없다.

2. 벨만포드 

    장점 : 음의 간선이 존재할때 최단거리를 구할 수 있다.

    단점 : 음의폐로가 존재할 수 있다. / 시간이 오래걸린다.

3. 플로이드 워셜

    장점 : 하나의 정점에서 시작하여 다른 정점의 최단거리를 구하는 것이 아닌, 모든 정점을 기준으로 각 정점에 최단거리를 구한다.

    단점 : 시간이 오래 걸린다.

 

 

위처럼 장/단점이 존재하기에 여러 최단거리 알고리즘이 있는데, 이번에는 플리이드 워셜 알고리즘을 살펴보고자 한다.

위에서도 말했듯, 플로이드 워셜 알고리즘을 사용하게되면, 모든 시작 정점부터 모든 끝 정점까지의 최소거리를 구할 수 있다.

즉, NxN 형태의 행렬을 만드는 것이다.

 

그럼 한번 예제를 살펴보도록 하자.

위와같이 그래프를 하나의 행렬로 나타낼 수 있다.

 

플로이드 워셜은 간단하게 생각해서 브루트 포스(완전탐색)이라고 생각하면 편하다.

어떻게 진행하는지 일단 말로 표현해보겠다.

 

1. 경유지 노드 선택(via)

2. 시작, 목적지 노드 선택

3. (시작 ~ 경유지 거리 + 경유지 ~ 목적지 거리) < 목적지 최단거리라면 update

 

이 1~3과정을 모든 경유지( N개 )에 대해 수행하게 되면 모든 최단거리를 구할 수 있다. 굉장히 직관적이다. 한번 위의 예시로 풀어보겠다.

위 예제는 시작점이 3일때 최단거리를 update하는 것을 단적인 예로 보여준다.

여기서는 3->2로 가는 경로가 무한대였지만, 10으로 update한 것을 볼 수 있다. 

가장 핵심은 경유지(via node)를 통해 갔을때 기존에 가던 길이보다 작으면 update시켜준다는 것이다.

node N개만큼 모든 경우의 수를 구해야 하기때문에 계산량이 많아져서 위에는 단적인 예만 적어 놓았다.

 

알고리즘적으로는 알고나니 수월한 알고리즘인 것 같다.

혹시 문제를 풀고싶다면 밑에 백준 링크를 남겨놓을테니 풀어보길 바란다. 전형적인 플로이드 워셜 구현 문제이다.

https://www.acmicpc.net/problem/11404

11404번: 플로이드