최단거리 (Floyd_Warshall)

Floyd_Warshall

1.Floyd_Warshall 이란

• 플로이드 워셜 알고리즘은 '모든지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야할 경우' 사용한다.
• 총시간복잡도는 O(n^3)으로 많은 노드가 주어진 경우 사용하기 어렵다.
• 최단 거리를 저장하기 위해 1차원 리스트를 이용한 다익스트라와 다르게 모든 노드에서 다른 모든 노드로 가는 최단거리 정보를 담기위해 2차원 리스트를 처리해야한다.
• 점화식은 D(a,b) = min(D(a,b), D(a,k) + D(k,b) 이다. (A에서 B로가는 최소비용과 A에서 K를 거쳐 B로 가는 비용)을 비교하여 더 작은값으로 갱신한다. (직항과 경유의 비교)

2.예제코드

---

INF = int(1e9)

n = int(input())
m = int(input())

graph = [[INF] * (n + 1) for _ in range(n + 1)]   # 초기값을 무한대로 만든 2차원 리스트 선언

for a in range(1, n+1):   # 자기 자신에서 자기 자신으로 가는 비용은 0으로 초기화
  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])     # D(a,b) = min(D(a,b), D(a,k) + D(k,b))

for a in range(1, n + 1):
  for b in range(1, n + 1):
    if graph[a][b] == INF:
      print('INFINIY', end = ' ')
    else:
      print(graph[a][b], end = ' ')
  print()     # 결과를 행별로 띄어 출력하기 위해 선언