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

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

• 플로이드 워셜 알고리즘: 모든 지점에서 다른 모든 지점까지의 최단 경로를 구해야 하는 경우 사용할 수 있는 알고리즘

• 입력 예시

  # 노드 개수(n)
  4
  # 간선 개수(m)
  7
  # a, b, c: a 노드에서 b 노드로 가는 비용 c
  1 2 4
  1 4 6
  2 1 3
  2 3 7
  3 1 5
  3 4 4
  4 3 2

• 소스코드

  INF = int(1e9)
  
  n = int(input())
  m = int(input())
  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())
      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):
          if graph[a][b] == INF:
              print("INF", end = " ")
          else:
              print(graph[a][b], end = " ")
      print()

• 출력

  0 4 8 6
  3 0 7 9
  5 9 0 4
  7 11 2 0