알고리즘 선택에 도움을 주는 트리. 클릭해서 이동하시면 문제에 적용할 알고리즘을 찾을 수 있습니다.
대분류
그래프
최단경로
- 간선에 가중치가 없다면 ? -> dfs, bfs
| 알고리즘 | 시간 복잡도 | 구현 난이도 | 적용 문제 |
|---|---|---|---|
| dfs, bfs | O(V^2) with 인접행렬 O(V+E) with 인접리스트 | 쉬움 | 단어 변환 |
| 알고리즘 | 시간 복잡도 | 구현 난이도 | 적용 문제 |
|---|---|---|---|
| 다익스트라 | O(ElogV) with 우선순위 큐 & 인접리스트 or O(V^2) | 어려움 | |
| 벨만포드 | O(VE) | 중 | |
| 플로이드-워셜 | O(V^3) | 쉽다 | 합승 택시 요금 |
음의 가중치
- 음수 사이클이 있는가 ? -> 못구함. 벨만포드
O(VE)로 사이클 존재여부 알 수 있음 - 모든 점 모든 경로? -> 플로이드-워셜
O(V^3)