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

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

그래프에서 모든 노드 간에 최단 거리를 구하는 알고리즘

 

• 특징

- 음수 가중치 에지가 있어도 수행할 수 있다.

- 동적 계획법의 원리를 이용해 알고리즘에 접근한다.

- 시간복잡도 : O(V³) (노드 수 : V)

 

 

플로이드-워셜 핵심 이론

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

 

• 플로이드-워셜 점화식

D[S][E] = min(D[S][E], D[S][K] + D[K][E])

 

 

플로이드-워셜 알고리즘 구현 방법

1. 배열을 선언하고 초기화한다.

[ 예시 ]

 

• D[S][E] : 노드 S에서 노드 E까지의 최단 거리를 저장하는 배열
• 초기화

  - S == E ⇒ D[S][E] = 0 (자기 자신에게 가는 데 걸리는 최단 경로값)

  - S != E ⇒ D[S][E] = ∞

 

 

2. 최단 거리 배열에 그래프 데이터를 저장한다.

[ 예시 ]

 

• D[S][E] = W

  - S : 출발 노드

  - E : 도착 노드

  - W : 에지의 가중치

 

 

3. 점화식으로 배열을 업데이트한다.

[ 예시 ]

 

점화식을 3중 for문의 형태로 반복하면서 배열의 값을 업데이트한다.

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

- 완성된 배열은 모든 노드 간의 최단 거리 정보를 표현한다.

 

 

 

 

 

* <Do It! 알고리즘 코딩테스트 with C++편>, <이것이 취업을 위한 코딩 테스트다 with 파이썬>을 참고하였습니다.