반응형
📍 정의 및 특징
가중치가 있는 그래프에서 특정 출발 노드 → 다른 모든 노드까지의 최단 경로 탐색
- 음수 가중치 에지가 있어도 수행 가능
- 음수 사이클 존재 여부 판단
- 시간 복잡도 : O(VE)
#가중치O #음수사이클
+ DP 활용
📍 필요 변수
1. 에지 클래스
- 노드 변수 2개 (start, end)
- 가중치 변수
2. 그래프 에지 리스트
- ArrayList<Edge>
3. 최단 경로 배열
- int[]
- 출발 노드 : 0 / 나머지 노드 : ∞
4. 사이클 판단 변수
- boolean
📍 실행 과정
- 그래프 에지 리스트 & 최단 경로 배열 초기화 (출발 노드 : 0 / 나머지 : ∞)
- 모든 에지
E = (s,e,w)확인해 정답 배열 업데이트 → (노드 개수 - 1)번 반복
⇒D[s] ≠ ∞ & D[e] > D[s] + w이면,D[e] = D[s] + w로 업데이트 - 모든 에지 한 번 더 반복해 음수 사이클 유무 확인
(업데이트 되는 노드가 있으면, 음수 사이클 존재하는 것)
➕ 예제
[백준/JAVA] 11657번: 타임머신
🔺 문제 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10
bono039.tistory.com
(참고)
Do it 알고리즘 코딩 테스트 자바편
반응형
'코테 > 알고리즘' 카테고리의 다른 글
| 최소 신장 트리 (MST) - 크루스칼, 프림 (0) | 2023.06.27 |
|---|---|
| 플로이드-워셜 (0) | 2023.06.26 |
| 최단 경로 탐색 알고리즘 (0) | 2023.06.23 |
| 다익스트라 (0) | 2023.06.23 |
| 위상 정렬 (0) | 2023.06.23 |
