반응형
📍 정의 및 특징
모든 노드 간 최단 경로 탐색
- 음수 가중치 에지가 있어도 수행 가능
- DP 원리 이용 (점화식)
D[S][E] = Math.min(D[S][E], D[S][K] + D[K][E])
: A → B까지 최단 경로를 구할 때, 최단 경로 위에 K가 존재한다면 그것을 이루는 부분 경로 역시 최단 경로
- 노드 개수의 범위가 적은 경우 사용 (∵ 시간 복잡도가 빠른 편이 아니므로)
- 시간 복잡도 : O(V³)
📍 필요 변수
1. 최단 거리 배열
2. 인접 행렬
📍 실행 과정
- 최단 거리 배열 선언 · 초기화
-D[S][E] = if(S == E) ? 0 : ∞
- 최단 거리 배열에 인접 행렬 사용해 그래프 데이터 저장
- 플로이드-워셜 수행 : 점화식으로 배열 업데이트 → 3중 for문
➕ 예제
(참고)
Do it 알고리즘 코딩 테스트 자바편
반응형
'코테 > 알고리즘' 카테고리의 다른 글
트라이 (Trie) (0) | 2023.06.28 |
---|---|
최소 신장 트리 (MST) - 크루스칼, 프림 (0) | 2023.06.27 |
벨만-포드 (0) | 2023.06.26 |
최단 경로 탐색 알고리즘 (0) | 2023.06.23 |
다익스트라 (0) | 2023.06.23 |