다익스트라 vs BFS

오늘은 다익스트라(dijkstra)와 BFS의 차이점을 공부하겠습니다.

---

다익스트라 vs BFS

둘다 그래프 탐색 알고리즘 입니다. 두개의 차이점은 다음과 같습니다.

정점 V 간선 E

비교	다익스트라	BFS
사용 이유	가중치가 있는 그래프 탐색	가중치가 없는 그래프 탐색
시간 복잡도	O(VlogE)	O(VlogE)
탐색 방법	간선이 음수가 아닌 탐색 최단 거리 탐색(가중치 비용이 있음)	너비 탐색을 하여 최단 거리 탐색(가중치 비용이 없음)

출처 : https://velog.io/@kasterra/%ED%95%B5%EC%8B%AC-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EA%B7%B8%EB%9E%98%ED%94%84-%EC%B5%9C%EB%8B%A8-%EA%B2%BD%EB%A1%9C-%ED%83%90%EC%83%89

위와 같은 그림일 경우 BFS로 2번까지의 최단거리를 구할경우 0->(1,2)->3으로 BFS는 탐색하므로 매우 부적합

다익스트라는 0->1->3->2가 가능