[알고리즘]플로이드_워셜 알고리즘

플로이드-워셜 알고리즘

• 모든 정점 사이의 최단경로를 찾는 탐색 알고리즘

• 시간복잡도 O(n^3)

• 핵심은 해당 직접 방문하는 경로의 cost와, 다른 곳을 들렀다가 방문하는 cost 를 비교하여 더 작은 값을 선택해 나가는 것

예시 그래프

code

import sys
inf = sys.maxsize


n = 4 #int(input())
a = [[0,2,inf, 4], [2,0,inf, 5],[3,inf,0,inf],[inf,2,1,0]]
dist = [[inf]*n for _ in range(n)]

for i in range(n):
  for j in range(n):
    dist[i][j] = a[i][j] # a 를 dist에 할당


for k in range(n): # 거치는 점
  for i in range(n): # 시작점
    for j in range(n): # 끝점
      # K를 거쳐을 때의 경로가 더 적은 경로
      if dist[i][j] > dist[i][k] + dist[k][j]:
        dist[i][j] = dist[i][k] + dist[k][j] # 할당
  
print(dist)

Reference

• https://it-garden.tistory.com/247