플로이드 와샬(Floyd-Warshall) 알고리즘

👏 정의

• 그래프에서 가능한 모든 노드 쌍에 대해 최단 거리를 구하는 알고리즘이다.
• 시간 복잡도는 O(V^3)
• 시작점에 대한 모든 노드들의 최단거리를 구하는 다익스트라 알고리즘과 달리 모든 쌍에 대한 최단 거리를 구하고, 음의 가중치를 가지는 그래프에도 쓸 수 있다는 것이 특징이다.

🙌 플로이드 와샬 == 다이나믹 프로그래밍

플로이드 와샬 알고리즘은 제목에서 보는 것처럼 다이나믹 프로그래밍을 사용하는 알고리즘이다.

경유점

그래프에서 최단거리를 구하기 위해서는 크게 경로가 두가지로 나뉜다고 보았다.

1. i에서 j로 곧바로 가는 경로
2. i에서 다른 정점 k를 거쳐 j로 가는 경로

이들 중 작은 것을 최단 경로로 선택하면 된다.

반복문에서 k가 1부터 v번 정점까지 돌면서 각각의 정점을 지나는 경로를 선택할 것인지 결정한다.

만일 k를 거쳐간다면, i에서 k까지 결로 p1이 존재하게 된다. 이때 p1은 {1,2,...k-1}까지의 정점들을 선택할 것인지 이미 결정이 끝난 최단경로이다. 그리고 k에서 j까지의 경로 p2 또한 마찬가지이다.

플로이드 와샬은 다이나믹 프로그래밍으로 짜여졌기 때문에 점화식이 존재한다.

• 플로이드 와샬의 점화식
  

초기화

플로이드 알고리즘은 DP를 이용하며, 결과값을 만들어내기 전 초기화는 상당히 중요하다.

이때, 초기화는 다익스트라 알고리즘과 비슷하지만, 일차원 배열로 최단거리를 정보를 저장하는 다익스트라 알고리즘과 달리 이차원 배열로 최단거리 정보를 저장해야 한다.

1. 도달할 수 없는 정점들에 대해 모두 매우 큰 값(INF)을 넣어주어야한다.
2. 또한 자기자신에게 가는 간선의 가중치는 0으로 설정한다.
3. 그리고 나서 주어진 그래프에 값을 넣는다.

음수 간선의 존재 여부

음수의 간선 자체가 허용되지 않는 다익스트라 알고리즘에 비해 플로이드 와샬은 음수의 간선은 허용된다. 하지만 음수의 간선을 통해 아래의 그림과 같은 음수의 사이클에 갇히게 된다면 최솟값 계산에 차질이 생길 수 있기 때문에 음수의 사이클이 있는 그래프에서는 사용할 수 없다.

😉 플로이드 와샬 동작과정

1. 초기화 : 그래프를 준비, 최단거리 테이블을 초기화
   
2. Step 1: 1번 노드를 거쳐가는 경우를 고려, 테이블 갱신(k = 1)
   
3. Step 2: 2번 노드를 거쳐가는 경우를 고려, 테이블 갱신(k = 2)
   
4. Step 3: 3번 노드를 거쳐가는 경우를 고려, 테이블 갱신(k = 3)
   
5. Step 4: 4번 노드를 거쳐 가는 경우를 고려, 테이블 갱신(k = 4)
   

👏 백준 플로이드 코드 풀이

### 백준 11404 플로이드
## 그래프(플로이드 와샬)
# 모든 도시의 쌍(A,B)에 대해서 도시 A - B로 가는 데 필요한 비용의 최솟값을 구하라

import sys
input = sys.stdin.readline

INF = 100000000

n = int(input())
m = int(input())

# 그래프 초기화
graph = [[INF] * (n+1) for _ in range(n+1)]

# 그래프에 비용의 최솟값 삽입 
for _ in range(m):
    a,b,c = map(int, input().split())
    graph[a][b] = min(graph[a][b],c)

# 플로이드 와샬을 통해 최단 거리 구하기
for k in range(1,n+1):
    for a in range(1,n+1):
        for b in range(1, n+1):
            if a == b:
                graph[a][b] = 0
            else:
                graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])

# 그래프 출력
for i in range(1,n+1):
    for j in range(1,n+1):
        if graph[i][j] == INF:
            print(0, end = " ")
        else:
            print(graph[i][j], end = " ")
    print()