Algorithm/Study
2021. 9. 24.
최단 경로 알고리즘 : 플로이드 워셜
플로이드 워셜 알고리즘 개념 - 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우 사용하는 알고리즘 (↔ 다익스트라 알고리즘 : 한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우에 사용하는 알고리즘) - 매번 방문하지 않은 노드 중에서 최단 거리를 갖는 노드를 찾을 필요가 없다. - 2차원 리스트에 최단 거리 정보를 저장한다. - 시간 복잡도 : O(N^3) - 다이나믹 프로그래밍이다. (점화식 사용) Dab = min(Dab, Dak + Dkb) A에서 B로 가는 최소 비용과 A에서 K를 거쳐 B로 가는 비용을 비교하여 더 작은 값으로 갱신한다. 구현 INF = int(1e9) # 노드 개수, 간선 개수 n = int(input()) m = int(input()) #..
