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

플로이드 워셜 알고리즘

모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우에는 어떠한 알고리즘을 사용해야 할까?

그건 바로 플로이드 워셜 알고리즘이다.

짧막 복습 다익스트라 알고리즘

다익스트라 알고리즘은 start node에서 각 노드로 가는 최단 거리를 구해주는 알고리즘으로 인접 노드중 최단 거리 노드를 계속해서 선택해가며 거리를 갱신하는 방식으로 동작하는 알고리즘이다.

여기서 핵심은 방문하지 않은 노드에서 최단 거리를 고민할 필요가 없다는 사실이다.

플로이드 워셜 알고리즘과의 차이점

플로이드 워셜 알고리즘은 현재 노드를 거쳐 가는 모든 경로를 고려한다.
때문에 노드의 갯수가 N일때, 알고리즘상으로 N번의 단계를 수행하며 단계마다 O(N^2)의 연산을 통해 현재 노드를 거쳐 가는 모든 경로를 고려한다.

따라서 플로이드 워셜 알고리즘의 시간 복잡도는 O(N^3) 이다.

플로이드 워셜 알고리즘의 내용

shortestPath(i, j, k) 함수를 node i 에서 node j 로 k를 경유하거나 하지 않은 길 중에서 가장 짧은 길의 길이를 알려준다고 하자.
단 {k|k는 정수, 1 <= k <= N}

위의 최단거리는 아래의 case중에서 하나일 것이다.
1. i에서 j를 가되, k를 경유하지 않는 경우 (k-1 개의 노드의 조합으로 구성된 경우)
2. k를 경유하는 경우 (i~k 및 k~j 각각 k-1개의 노드의 조합으로 구성된 경우)

따라서 우리는 재귀식을 아래와 같이 쓸 수 있다.

base case

shortestPath(i, j, 0) == w(i, j)

reculsive case

shortestPath(i, j, k) == min(shortestPath(i, j, k-1), shortestPath(i, k, k-1) + shortestPath(k, j, k-1))

점화식으로 표현하면 아래와 같다.

Dist(a, b) = min(dist(a, b), dist(a, k)+dist(k, b))

파이썬으로 구현해보자

INF = int(1e9)

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

graph = [[INF] * (n+1) for _ in range(n+1)]

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

for _ in range(m):
   a, b, c = map(int, input().split())
   graph[a][b] = c

def floyd_warshall(graph):
   for k in range(1, n+1):
       for i in range(1, n+1):
           for j in range(1, n+1):
               graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])
   return graph

answer = floyd_warshall(graph)

for a in range(1, n+1):
   for b in range(1, n+1):
       if answer[a][b] == INF:
           print("INF", end=" ")
       else:
           print(answer[a][b], end=" ")
   print()