목록2023/09/30 (1)
Rootable의 개발일기
플로이드-워셜(Floyd-warshall) 알고리즘
📌 정의 시작점을 지정하지 않고 그래프에서 모든 노드와 관련된 최단 거리를 구하는 알고리즘 📌 주요 특징 기능 특징 시간 복잡도(노드 수: V) 모든 노드 간에 최단 경로 탐색 - 음수 가중치 Edge가 있어도 수행 가능 - 동적 계획법의 원리를 이용해 알고리즘에 접근 O(V^3) 📌 핵심 이론 최단 경로를 구했다고 가정했을 때, 그것을 이루는 부분 경로 역시 최단 경로이다. 예를 들어, A에서 B까지 최단 경로를 구했다고 가정한다. 이때, 해당 경로 위에 K 노드가 존재한다면 A에서 K 노드를 거쳐 B에 도착하는 경로 역시 최단 경로라는 것이다. 따라서 점화식은 다음과 같이 도출된다. D[S][E] = Math.min(D[S][E], D[S][K] + D[K][E]) 📌 접근 방법 🔎 초기 배열 D[S..
알고리즘
2023. 9. 30. 13:12