코딩테스트/기본 알고리즘
2022. 2. 23.
최단거리 (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(in..