문제 유형
- 도착 지점에서 여러 출발 지점까지의 최단경로를 구하는 경우
- 특정 노드(출발 지점이 고정되어 있지 않음)에서 도착 지점까지의 최소 비용을 시간초과 안나게 구해야 하는 경우
역방향 그래프 활용 이유
- 그래프의 가중치가 양수일 경우, 간선을 역으로 뒤집어도 최단 경로가 일치한다.
- 도착 지점을 기준으로 다익스트라 를 1번만 수행하면, 모든 출발 지점에서 도착 지점까지의 최단 경로를 한꺼번에 구할 수 있다.
예시
- 문제 : 여러 도시에서 한 중앙 도시로 최소 비용 이동을 구하는 경우
- 해결 : 간선을 역방향으로 뒤집고 중앙 도시에서 모든 도시로 가는 다익스트라를 수행하면, 모든 모시에서 중앙 도시로 가는 최단 경로를 1번에 구할 수 있다.
'자료 구조 & 알고리즘(Data Structure & Algorithm) > 알고리즘(Algorithm)' 카테고리의 다른 글
| [알고리즘] 위상정렬 복습 겸 정리 (1) | 2024.12.20 |
|---|---|
| [알고리즘] 최소신장트리(Minimum Spanning Tree) 복습 겸 정리 (2) | 2024.11.27 |
| [알고리즘] 유니온 파인드 알고리즘(Union-Find) 복습 겸 정리 (0) | 2024.11.27 |
| [알고리즘] 다익스트라 알고리즘(Dijkstra Algorithm) 기초 (0) | 2024.11.21 |