CHAPTER 9. 최단 경로 - 플로이드 워셜

플로이드 워셜 알고리즘

모든 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘

특징

• 3중 반복문 이용
• 2차원 리스트에 최단 거리 정보를 저장 = 인접 행렬
• 노드 개수가 적은 경우에 사용
• N개 노드에 대해 점화식에 맞게 2차원 리스트를 갱신 → 다이나믹 프로그래밍

시간 복잡도

• N개 노드가 있으면 N번의 단계를 수행한다.
• 각 단계마다 해당 노드를 거쳐 가는 경우를 고려한다.
  • A → 노드 → B 의 비용을 확인하고 최단 거리를 갱신한다.
  • 즉, 현재 노드를 제외하고 N-1개의 노드 중 서로 다른 노드 (A, B)쌍을 선택한다.$O(P_{N-1}^2) = O(N^2)$
• K번 노드를 볼 때, 구체적인 점화식은 $D_{ab} = min(D_{ab}, D_{ak}+D_{kb})$ 이다.
  • A에서 B로 가는 최소 비용과 A에서 K를 거쳐 B로 가는 비용을 비교하여 더 작은 값으로 갱신
• 전체 시간 복잡도는 $O(N^3)$이다.

동작 과정

• 최단 거리 정보를 저장하는 2차원 리스트를 초기화 한다.
  • 노드 자기 자신: 0
  • 연결된 노드: 해당 간선의 비용
  • 연결되지 않은 노드: 무한
• 1번 노드부터 순서대로 노드를 거쳐서 가는 경우를 고려한다.
  • 기존의 A에서 B로 가는 비용보다 A-K-B로 거쳐서 가는 비용이 작다면 최단 거리 정보를 갱신한다.

구현

  

    
    
    
    
  
# 플로이드 워셜 알고리즘 소스코드
INF = int(1e9) # 무한을 의미하는 값 10억

n = int(input()) # 노드 개수
m = int(input()) # 간선 개수

# 최단 거리 정보를 저장하는 2차원 리스트
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 # 비용으로 0으로 설정

for i in range(1, n+1):
  graph[i][i] = 0

# 간선 m개의 정보를 입력 받아 그 값으로 초기화
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 + K→B 비용을 비교
      
# 수행 결과 출력, 2차원 리스트 형태로 출력
for a in range(1, n+1):
  for b in range(1, n+1):
    # 도달할 수 없는 경우 INFINITY라고 출력
    if graph[a][b] == INF:
      print("INFINITY", end=' ')
    else:
      print(graph[a][b], end=' ')
  print()