bfs 는 depth 기준으로 먼저 탐색하다보니 "최소 경로" 문제에 은근 많이 사용되는 것 같다. 이번에는 디익스트라 문제였던 것 같았는데 bfs 가 사용된 경우가 있어서 한 번 정리(?) 해 본다.
안전한걸 선호해서 그런지, 나는 위에서부터 차근 차근 모두 살펴보고 내려가는 느낌의 bfs 를 dfs 보다 선호하는 편이다.
bfs 의 시간복잡도
- O(V+E)
- bfs 는 모든 간선이 단위길이(동일한 w) 로 이루어져 있을 때, 방문하는 시점마다 해당 정점에 대한 최단 경로를 구하는 것이 된다. 따라서 디익스트라 보다 빠른 경우가 존재한다.
디익스트라는 A 로부터 모든 노드까지의 최소거리를 측정하는데 사용된다.
간선들의 비용들이 서로 다르고, 어떤 노드까지의 최소 비용이 지속적으로 업데이트 되는 경우라면 디익스트라를 사용해야 할 것이다.
디익스트라의 시간복잡도 ( PQ 를 사용해 구현한 Dikstra)
- O((E+V)logV)
PQ 에 들어갈 수 있는 원소들의 개수는 V^2 이다.
- O(logV2) = O(2logV) = O(logV)
PQ 에서 꺼낸 원소들에 대해
O(VlogV) -> 꺼내서 어떤 연산을 하는 노드의 개수는 V 개다
O(ElogV) -> 해당 노드의 "인접 노드" 들의 최소 경로를 업데이트 한다
번외 : PQ 가 아닌, 선형으로 "현재 최소 비용을 갖는 노드를 탐색하는" 방식의 Dikstra
- O(V^2 + E)
- 이 때는, 현재 최소 비용을 갖는 노드를 탐색하기 위해, 최소비용테이블을 선형으로 탐색해야만 한다. 따라서 여기에는 O(V) 라는 시간이 든다.
참고
