[알고리즘] 플로이드 워셜

최단경로 알고리즘이며 모든 노드에서 모든 노드로부터 최단경로를 구할 때 사용하는 알고리즘이다.

 

플로이드 워셜 vs 다익스트라

저번 시간에 다뤘던 한 지점에서 모든 노드로의 최단경로를 구하는 다익스트라 알고리즘과 플로이드 워셜은 다르다.

다익스트라 알고리즘은 1차원 리스트를 이용하지만 플로이드 워셜 알고리즘은 2차원 리스트를 사용한다. 

또한 다익스트라는 방문하지않은 노드 중에서 최단경로를 찾지만 플로이드 워셜은 방문하지않았는지 했는지 관심이 없다.

 

플로이드 워셜의 점화식

노드의 개수가 N일 때 N번 만큼 2차원 리스트를 갱신하다. 1~N번까지의 노드를 한번씩 K로 정해준 뒤 K를 제외한 N-1개의 노드 중에서 서로 다른 노드 A, B를 고른다. K를 거쳐가는 A-K 경로와 K-B 경로의 가중치를 더해서 기존에 있던 값과 비교해 작다면 초기화해준다. 이런 방식으로 2차원 리스트를 최신화하기에 방문을 했는지 안했는지는 중요하지않아진다.  결과적으로 플로이드 워셜의 점화식은 G[a][b] = min(G[a][b], G[a][k] + G[k][b]) 이다.

 

플로이드 워셜 알고리즘 단계

1, 모든 원소가 INF(무한)인 2차원 리스트를 작성한다.

INF = int(1e9)

# 노드의 개수
n = int(input())
# 간선의 개수
m = int(input())
# 2차원 리스트 작성
graph = [[INF] * (n+1) for _ in range(n+1)]

2, 자기 자신으로부터 자기 자신으로 이동하는 경로는 0이기에 0으로 최신화해준다.

# n은 노드의 개수다. (1~n의 노드가 존재)
for a in range(1, n+1):
	for b in range(1, n+1):
    		if a == b:
        		graph[a][b] = 0

3, 각 간선으로부터 정보를 받아서 초기화 해준다.

# 간선의 정보들이 공백을 간격으로 주어진다면
for _ in range(m):
	a, b, c = map(int, input().split())
    	graph[a][b] = c

4,  플로이드 워셜 알고리즘을 실행해준다.

for k in range(1, n+1):
	for a in range(1, n+1):
    		for b in range(1, n+1):
        		graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])

5 문제에 알맞게 필요한 2차원 리스트의 값을 뽑아주면된다.

 

아래는 플로이드 워셜 알고리즘 적용이 가능한 문제이다.

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

10159번: 저울