플로이드 와샬 (Floyd Warshall)

플로이드 와샬 역시 벨만 포드나 다익스트라와 같은 최단 경로 찾기 알고리즘입니다. 다만, 1:N 최단 경로를 찾는 벨만 포드와 다익스트라와 달리, 플로이드 와샬은 N:N 사이의 최단 경로를 찾습니다. 그렇기 때문에 비용을 저장하는 배열로 이중 배열을 사용하게 됩니다. 순환만 발생하지 않는다면 음수 가중치도 가능하며, 기본적으로 동적계획법으로 접근하게 됩니다.

 

플로이드 와샬은 가능한 모든 경유지에 대해 모든 정점에서 모든 정점으로 가는 최단거리를 확인하기 때문에, 시간복잡도는 O(N^3)이 나옵니다. 역시 n:n 경로라 그런가 다른 알고리즘들보다 시간이 많이 걸리네요ㅎ..

 

 

 

먼저 플로이드 와샬을 구현하기 위해서 좀 복잡하지만 아래와 같은 그래프를 사용하겠습니다. 그래도 보는사람 쉽게 보시라고 제가 색도 다르게 표현했어요... :) 그래프는 백준 11780번을 참고했습니다.

 

구현은 Swift언어를 사용했고, 플로이드 와샬을 구현하기 위해 아래와 같은 단계를 따랐습니다.

 

 

 

1️⃣비용을 저장하기 위한 이중 배열을 무한(저는 999999로 줬습니다)으로 초기화 합니다. 단, 자기 자신으로 가는 길은 0으로 초기화합니다.

 

2️⃣각 버스(간선)의 비용을 입력받아 배열에 저장해줍니다.

여기까지 진행하고 cost 배열을 출력하면, 아래와 같이 입력받은 버스 비용이 적용되어 있을 거예요!

 

3️⃣출발지-경유지-도착지 에 대한 모든 경우의 수를 체크해줍니다.

 

 

그럼 끝이예요!

이 과정을 모두 거치고 난 후에 cost 배열을 출력하면 아래와 같이 N:N 사이의 최단 비용이 나옵니다. 생각보다 간단하죠? :)