[Algorithm] 플로이드-워셜 (Floyd-Warshall) 알고리즘

플로이드 워셜 알고리즘

그래프에서 최단 거리를 구하는 알고리즘

 

기능	특징	시간 복잡도 (노드 수:V)
모든 노드 간에 최단 경로 탐색	- 음수 가중치 에지가 있어도 수행할 수 있음. -동적 계획법의 원리를 이용해 알고리즘에 접	O(V^3) (V의 세제곱)

 

 

핵심 이론

플로이드-워셜 알고리즘은 도출하는 가장 핵심적인 원리는 A 노드에서 B 노드까지 최단 경로를 구했다고 가정했을 때 최단 경로 위에 K 노드가 존재한다면 그것을 이루는 부분 경로 역시 최단 경로라는 것이다.

 

색칠된 에지 경로가 1-> 5 최단 경로라면 1->4 최단 경로와 4->5 최단 경로 역시 색칠된 에지로 이뤄질 수 밖에 없다.

즉, 전체 경로의 최단 경로는 부분 경로의 최단 경로의 조합으로 이뤄진다는 뜻이 된다.

이 원리로 다음과 같은 점화식을 도출할 수 있다.

 

도출한 플로이드-워셜 점화식
D[S][E] = Math.min(D[S][E], D[S][K] + D[K][E])

 

구현 방법

 

1. 리스트를 선언하고 초기화하기

 

D[S][E] 는 노드 S에서 노드 E까지의 최단 거리를 저장하는 리스트라 정의한다.

S와 E의 값이 같은 칸은 0, 다른 칸은 ∞로 초기화한다.

여기에서 S==E 는 자기 자신에게 가는 데 걸리는 최단 경로 값을 의미하기 때문이다.

 

2. 최단 거리 리스트에 그래프 데이터 저장하기

 

출발 노드는 S, 도착 노드는 E, 이 에지의 가중치는 W라고 했을 때 D[S][E] = W 로 에지의 정보를 리스트에 입력한다.

이로써 플로이드 - 워셜 알고리즘은 그래프를 인접 행렬로 표현한다는 것을 알 수 있다.

 

 

 

3. 점화식으로 리스트 업데이트하기

기존에 구했던 점화식을 3중 for 문의 형태로 반복하면서 리스트의 값을 업데이트한다.

 

플로이드-워셜 알고리즘 로직

for 경유지 K에 관해 (1 ~ N)   # N: 노드 개수
      for 출발 노드 S에 관해 (1 ~ N)
         for 도착 노드 E에 관해 (1 ~ N)
               D[S][E] = Math.min(D[S][E], D[S][K] + D[K][E])

 

 

 

• 플로이드-워셜 알고리즘 로직에서 가장 중요한 부분(외워야 하는 부분)
• 3중 for문을 하는데, 가장 바깥쪽이 K이다. 
• 점화식

 

• 최단 거리 리스트가 가지는 의미는 모든 노드 간의 최단거리를 표현한다.
• 예를 들어 1번 노드에서 5번 노드까지 가는 최단 거리는 D[1][5] = 6으로 나타난다는 것을 알 수 있다.
• 무한대로 표현된 경우는 못 가는 뜻.

 

플로이드-워셜 알고리즘은 모든 노드 간의 최단 거리를 확인해 주기 때문에 시간 복잡도가 O(V^3)으로 빠르지 않은 편이다. 

이에 따라 플로이드-워셜 알고리즘을 사용해야 하는 문제가 나오면 일반적으로 노드 개수의 범위가 다른 그래프에 비해 적게 나타나는 것을 알 수 있다.

 

 

• 참고자료: 인프런 Do it! 알고리즘 코딩테스트 with Python
• https://www.inflearn.com/course/lecture?courseSlug=%EB%91%90%EC%9E%87-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8-%ED%8C%8C%EC%9D%B4%EC%8D%AC&unitId=148399