20250122 이것이 코딩 테스트다 챕터9(최단 경로)

플로이드 워셜 알고리즘

앞서 본 다익스트라 알고리즘은 ‘한 지점에서’ 다른 특정 지점까지의 최단 경로를 구해야 하는 경우에 사용하는 최단 경로 알고리즘.

‘모든 지점에서’ 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우에 사용할 수 있는 알고리즘.
노드의 개수가 N개일 때 알고리즘상으로 N번의 단계를 수행하며, 단계마다 O(N^2)의 연산을 통해 ‘현재 노드를 거쳐 가는’ 모든 경로를 고려함.
따라서 총시간 복잡도 O(N^3)

모든 노드에 대하여 다른 모든 노드로 가는 최단 거리 정보를 담아야 하기 때문에 2차원 리스트에 ‘최단 거리’ 정보를 저장한다.

다익스트라 알고리즘은 출발 노드가 1개이므로 1차원 리스트에 ‘최단 거리’ 정보를 저장했음.

노드의 개수가 N개일 때, N번 만큼의 단계를 반복하며 ‘점화식에 맞게’ 2차원 리스트를 갱신하기 때문에 ‘다이나믹 프로그래밍’으로도 분류됨.

다익스트라 알고리즘은 그리디 알고리즘이었음.

원리

각 단계에서 해당 노드(지점)를 거쳐 가는 경우를 고려하면 됨.

1. 현재 확인하고 있는 노드를 제외한 N - 1개의 노드 중에서 서로 다른 노드 (A, B) 쌍을 선택함.
   
2. A -> 현재 확인하고 있는 노드 -> B로 가는 비용을 확인한 뒤 최단 거리 갱신.
   

즉, N-1P2개의 쌍을 단계마다 반복해서 확인하면 됨.
O(N-1P2)는 O(N^2)의 시간복잡도를 가지므로 전체 시간 복잡도가 O(N^3)이 되는 것.

점화식

D(ab) = min(D(ab), D(ak) + D(kb))
‘a에서 b로 가는 최소 비용’과 ‘a에서 k를 거쳐 b로 가는 비용’을 비교해 더 작은 값으로 갱신하겠다는 의미.
즉, ‘바로 이동하는 거리’가 ‘특정한 노드를 거쳐서 이동하는 거리’보다 더 많은 비용을 가진다면 이를 더 짧은 것으로 갱신한다는 것.

최단 거리 테이블

• 초기 설정
  ‘연결된 간선’은 단순히 그 값 채워 넣고, 연결되지 않은 간선은 ‘무한(int(1e9))’값으로 채움.
  자기 자신에서 자기 자신으로 가는 비용은 0이므로, 1 <= i <= n의 범위를 가지는 모든 i에 대해서 D(ii)는 0으로 초기화. (왼쪽 위에서 오른쪽 아래로 내려가는 대각선에 놓인 모든 원소 : 0)
  
  

• D(ab)
  a에서 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

# 각 간선에 대한 정보를 입력받아, 그 값으로 초기화
for _ in range(m):
  # A에서 B로 가는 비용은 C라고 설정
  a, b, c = map(int, input().split())
  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])

# 수행된 결과를 출력
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()

---