[알고리즘] 플로이드 워셜 최단 경로 알고리즘 파이썬 구현

자료 출처: https://youtu.be/acqm9mM1P6o

1. 플로이드 워셜 알고리즘

최단 경로 알고리즘으로, 모든 노드에서 다른 모든 노드까지의 최단 경로를 구하는 알고리즘

• 다익스트라 알고리즘의 경우 한 노드에서 다른 모든 노드까지의 최단 경로를 구하는 알고리즘인데 반해, 플로이드 워셜 알고리즘은 모든 노드에서 다른 모든 노드까지의 최단 경로를 구한다는 점이 차이점이다.
• 거쳐가는 노드를 기준으로 알고리즘을 수행하는 것은 다익스트라 알고리즘과 동일하나, 매 단계마다 방문하지 않은 노드 중 최단 거리를 갖는 노드를 찾는 과정이 필요 없다는 점이 다르다.
• 2차원 테이블에 최단 거리 정보를 저장한다.
• 다이나믹 프로그래밍 유형에 속하며, 삼중 반복문을 사용한다.
  • 시간 복잡도는 O(N^3)
  • 노드의 개수가 500개 미만일 때 사용 가능
• 각 단계마다 특정 노드 k를 거쳐가는 경우를 확인한다.
  • a에서 b까지의 최단 경로 vs a에서 k를 거쳐 b로 가는 거리
  • 점화식: Dab = min(Dab, Dak + Dkb)

2. 플로이드 워셜 알고리즘 구현

n, m = map(int, input().split())
inf = int(1e9)

# 그래프 초기화(2차원 리스트)
# 노드 넘버이기 때문에 (n + 1)을 곱해줌
# [inf]가 (n + 1)개 만큼 들어있는 리스트를 다시 (n + 1)개만큼 만들어 새로운 리스트에 넣어줌
graph = [[inf] * (n + 1) for _ in range(n + 1)]

# 모든 노드들에 대하여 자기 자신에게 가는 비용은 0으로 초기화
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()) # a에서 b로 가는 비용은 c
    graph[a][b] = c
    
# 모든 노드들에 대하여 a에서 b로 가는 최단 경로 업데이트하기
for k in range(1, n + 1): # k는 거쳐가는 노드
    for a in range(1, n + 1): # a는 출발 노드
        for b in range(1, n + 1): # b는 도착 노드
            graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])