최단 경로 알고리즘 - 플로이드 워셜 알고리즘 (feat.백준 11404번)

플로이드 워셜 알고리즘의 특징: 모든 지점에서 다른 모든 지점까지의 최단 경로를 구할 수 있음.

플로이드 워셜 알고리즘은 다이나믹 프로그래밍 방식으로 진행됨.

 

다익스트라 최단 경로 알고리즘은 한지점이 고정이였고, 그 지점으로부터 다른 모든 지점까지의 최단경로를 구하는 알고리즘이였음.

 

다익스트라 알고리즘은 단계마다 현재까지 최단 거리를 갖는 노드를 하나씩 반복적으로 선택했었다. 그리고 이 노드를 거쳐서 다른 노드로 가는 거리를 구해서, 최단 거리 테이블을 갱신하고 우선순위 큐에 해당 간선들을 추가해서 넣었음.

 

플로이드 워셜 알고리즘은 매우 단순하다. 매번 방문하지 않은 노드들 중 한가지를 골라서 그 노드를 거쳐가는 최단 경로와 지금까지 구한 최단 경로를 비교해서 테이블을 갱신시킴. 

Dab가 a에서 b로 가는 현재까지의 최단 경로 거리라고 하면, k노드를 거쳐가는게 더 짧을지 고민하는 점화식은 다음과 같다.

Dab = min( Dab, Dak + Dkb)

 

플로이드 알고리즘으로 푸는 백준 11404번에 대한 코드는 아래와 같다. 

플로이드 워셜 알고리즘으로 푸는 백준 11404번

여기서 간선 입력을 받는 부분에서 if문이 들어간 이유는 11404번 문제에서 한 정류장에서 다른 정류장으로 가는 버스가 한 개가 아닐 수 있다는 조건 때문임. 우리는 최단 경로 거리만 구하면 되므로, 시작점과 도착점이 같은 버스라면 더 빨리 가는 버스만 고려하면 됨.

 

플로이드 워셜 알고리즘은 for문 세개가 중첩된 매우 간단한 형태임. 때문에 시간 복잡도도 O(n^3)이다.

 

코드는 나동빈님의 '이것이 코딩테스트다' 를 참고했습니다.