알고리즘/알고리즘 개념
플로이드 워셜 알고리즘
0. 플로이드 워셜 알고리즘이란? - 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우에 사용 - 매 단계마다 현재 노드를 거쳐 가는 노드를 기준으로 알고리즘을 수행 - DP - 최단 거리 정보 저장 1. 알고리즘 진행과정 0️⃣ 초기 거리 테이블 설정 - 연결되지 않은 간선에는 무한대 - 자기 자신은 0 - 이외 간선들은 주어지는 거리 1️⃣ N번 돌면서 현재 노드 선택 >> 현재 노드를 거쳐서 지나가는 모든 경우를 고려 2️⃣ N^2번 돌면서 현재 노드를 거쳐 가는 모든 경로 순회 3️⃣ 원래 기록된 거리보다 현재 노드를 거쳐서 지나가는 거리가 더 짧다면 갱신 (직접 연결된 간선은 업데이트 X) -> O(N^3)의 시간복잡도를 가진다 2. 점화식 D[i][j] = min(D[i]..
