[알고리즘] 플로이드 워셜, 그것이 알고싶다

 

 

최단 경로 알고리즘,

마지막으로 플로이드 워셜 알고리즘을 알아봅시다!

 

---

 

# 플로이드 워셜 알고리즘이란?

모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우에 

사용하는 최단 경로 알고리즘입니다.

 

 

다익스트라 알고리즘과의 비교

• 다익스트라
  • 단계마다 최단 거리를 가지는 노드를 하나씩 선택해서, 경로를 확인하며 최단 거리 테이블을 갱신
  • 그리디 알고리즘
• 플로이드 워셜
  • 단계마다 거쳐 가는 노드를 기준으로 알고리즘 실행
  • DP 알고리즘

즉, 플로이드 워셜은 최단 거리를 갖는 노드를 찾는 게 아니라, 거쳐가는 노드를 확인합니다.

 

 

 

# 플로이드 워셜 알고리즘의 시간 복잡도

노드의 갯수가 N개 일 때, N번의 단계를 수행하며,

단계마다 O(N^2)의 연산을 통해 현재 노드를 거쳐가는 모든 경로를 고려하므로

총 시간 복잡도는 O(N^3)이 됩니다.

 

 

 

---

# 문제로 풀어보면서 이해하기

백준 11404 플로이드 문제를 통해 파이썬으로 플로이드 워셜 문제를 구현해봅시다.

도시가 n개 있고, 버스가 m개 있을 때, 각각 도선에 대한 비용이 있고

비용은 자연수이며 모든 도시 간의 최소 비용을 구하는 문제이므로

1. 간선의 값이 음수가 아님(= 벨만포드 아님)

2. 모든 도시 간의 비용을 구해야 함(= 다익스트라 아님)

의 근거를 통해 플로이드 워셜 문제임을 알 수 있습니다.

 

import sys

n = int(sys.stdin.readline())	# 도시 개수(노드)
m = int(sys.stdin.readline())	# 버스 개수(간선)
# 최소 거리를 담을 DP(DP[i][j]는 i도시에서 j도시를 갈 때의 최소 거리)
DP = [[float('inf') for _ in range(n + 1)]for _ in range(n + 1)]

# 시작점 = 끝점 이면 0으로 세팅
for i in range(n + 1):
    DP[i][i] = 0

for _ in range(m):
    # a도시에서 b도시 가는데 c의 비용이 든다.
    a, b, c = map(int,sys.stdin.readline().split())
    # 현재 저장되어 있는 값과 새로 온 값 비교해서 작은 걸로 넣기
    DP[a][b] = min(DP[a][b], c)

# 여기가 플로이드 워셜 알고리즘
# 반복문을 세번 돌려주면서
for k in range(1, n + 1):
    for p in range(1, n + 1):
        for q in range(1, n + 1):
            '''
            p에서 q까지 갈 때, 
            기존에 저장된 값과 k도시를 거쳐서 가는 것 중 
            어떤게 더 빠른지 계산해준다.
            '''
            DP[p][q] = min(DP[p][q], DP[p][k] + DP[k][q])

for i in range(1, n + 1):
    for j in range(1, n + 1):
        if DP[i][j] == float('inf'):
            DP[i][j] = 0
    print(*DP[i][1:])

 

 

---

이렇게 최단 경로 알고리즘 세가지를 알아봤는데요,

필요한 상황에 맞춰서 잘 골라서 구현하는 연습을 해봅시다!

---