[알고리즘] Floyd Warshall Algorithm

Floyd Warshall Algorithm 이란?

모든 정점에서 모든 정점으로 가는 최단거리를 구하는 알고리즘

 

특징

• 가중치/비가중치 그래프 모두에서 최단거리를 도출해낼 수 있다
• 음수 가중치를 가져도 사용가능하다 (단, cycle이 있고 가중치의 총 합이 음수인 경우엔 성립하지 않는다)
• 시간복잡도가 O(V³) 이다
• 다이나믹 프로그래밍(DP)을 사용하는 알고리즘이다

---

Floyd Warshall Algorithm 동작 과정

1. 모든 노드 무한대로 초기화
2. 자기 자신에게 가는 간선의 가중치는 0으로 설정 ( i -> i )
3. 나머지 노드 방문하며 주변 노드에 방문하는 최단거리 갱신
  - i 에서 j 로 가는데에 크게 두가지 경우로 나뉘고, 이 두가지 경우 중 최소값을 선택
    1) i 에서 j 로 가는 경로
    2) i 에서 k 를 거쳐 j 로 가는 경로
4. 음수 사이클이 존재하는지 확인
  - 자기 자신에게 가는 간선의 가중치가 음수인 경우, 그래프에 음수 사이클이 존재한다 ( adj[i][i] < 0 )

---

Floyd Warshall Algorithm 구현 소스

아래는 관련 알고리즘 문제인 '플로이드' 소스이다.

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

11404번: 플로이드

n = int(input())
m = int(input())
busCharge = [[100] * n for _ in range(n)]

for i in range(m):
    a, b, c = list(map(int, input().split()))
    busCharge[a-1][b-1] = min(busCharge[a-1][b-1], c)

for i in range(n):
    busCharge[i][i] = 0

for k in range(n):
    for i in range(n):
        for j in range(n):
            busCharge[i][j] = min(busCharge[i][j], busCharge[i][k] + busCharge[k][j])

for i in range(n):
    row = ""
    for j in range(n):
        row += str(busCharge[i][j]) + " "

---

시간복잡도 & 공간복잡도

코드에서 알 수 있듯이 정점의 개수 V만큼 반복분이 3중으로 수행되고 있기 때문에 O(V³)의 시간 복잡도를 갖는다.
그리고 간선들의 정보를 V∗V 크기의 인접행렬에 담았기 때문에 O(V²)의 공간 복잡도를 갖는다.