[알고리즘] Shortest Path / Floyd-Warshall

플로이드 워셜 알고리즘

플로이드 워셜(Floyd-Warshall) 알고리즘

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

노드의 개수가 N개일 때 알고리즘상으로 N번의 단계를 수행하며, 단계바다 O(N^2)의 연산을 통해 현재 노드를 거쳐가는 모든 경로를 고려
총 시간 복잡도는 O(N^3)

플로이드 워셜 알고리즘은 다익스트라 알고리즘과 다르게 2차원 리스트에 최단 거리 정보를 저장
2차원 리스트를 처리해야 하므로 N번의 단계에서 매번 O(N^2)의 시간이 소요

노드의 개수가 N개일 때 N번의 단계를 반복하며 점화식에 맞게 2차원 리스트를 갱신
다이나믹 프로그래밍 특징을 가진다.

각 단계에서는 해당 노드를 거쳐가는 경우를 고려
현재 확인하고 있는 노드를 제외하고 N-1개의 노드 중 서로 다른 노드 쌍을 선택
기존의 거리와 거쳐가는 거리를 비교하여 최단 거리 갱신

$D_{ab} = min(D_{ab}, D_{ak} + D_{kb})$

현재 노드가 k일 때 a에서 b로 가는 최단 거리($D_{ab}$) 갱신

최단 거리 테이블
2차원 리스트로 연결된 간선은 그 값을 채우고 연결되지 않은 간선은 무한으로 채운다
자기 자신으로 가는 거리는 0

import sys

intput = sys.stdin.readline
INF = int(1e9) #무한을 의미하는 값, 10억

n, m = map(int, input().split()) #노드의 개수 n, 간선의 개수 m

graph = [[INF]*(n+1) for _ in range(n+1)] #2차원 리스트(그래프 표현), 모든 값 무한을 초기화

for i in range(1, n+1):
  for j in range(1, n+1):
    if i == j:
      graph[i][j] = 0 #자기 자신으로 가는 비용 0으로 초기화

for _ in range(m): #각 간선에 대한 정보
  a, b, c = map(int, input().split()) #a에서 b로 가는 거리 c
  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):
      graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b]) #a에서 b로 가는 거리, a에서 k를 거쳐 b로 가는 거리 비교

#수행된 결과 2차원 리스트 출력
for i in range(1, n+1):
  for j in range(1, n+1):
    if graph[i][j] == INF: #도달할 수 없는 경우
      print('INFINITY', end=' ')
    else:
      print(graph[i][j], end=' ')

  print() #한 행 출력 후줄바꿈

참고

나동빈(2020).이것이 취업을 위한 코딩 테스트다 with 파이썬.한빛미디어