[CS] 다익스트라 알고리즘의 시간 복잡도
2023. 9. 19. 12:08ㆍCS
각 간선마다 힙에 넣는다고 하면 E * log(E) 각 간선마다 하는 이유는 다익스트라는 모든 간선을 돌게 되어 있기 때문이다.
그런데 V^2 > E라면 즉 sparse하다면 E * log(V)가 된다.
Reference
https://ds-jungsoo.tistory.com/7
Shortest Paths(다익스트라 알고리즘 (Dijkstra Algorithm))
이번에는 다익스트라 알고리즘에 대해서 공부를 해보았다. 다익스트라 알고리즘은 단일 시작점으로부터 다른 노드들까지의 최단 경로를 구하는 알고리즘이다. 또한, 음의 가중치를 허용하지
ds-jungsoo.tistory.com
'CS' 카테고리의 다른 글
| [CS] 에라토스테네스의 체 시간복잡도 (0) | 2023.09.21 |
|---|---|
| [CS] 정렬에 대한 나름의 이해 (0) | 2023.09.20 |
| [CS] 알고리즘의 두 기둥 (2) | 2023.09.19 |
| [CS] 다익스트라에 대한 나름의 이해 (0) | 2023.09.16 |
| [Java] Thread에 관해 적을 만한 것 (0) | 2023.09.08 |