codedoc

BFS탐색, 다익스트라 알고리즘 비교 본문

정리

BFS탐색, 다익스트라 알고리즘 비교

quince; 2016. 1. 17. 23:13
정점 V개 간선 E개가 존재한다고 하자.

용도
BFS탐색: 시작점으로부터 어떤지점까지 너비우선적으로 탐색한다. 최단경로를 구할 때 사용할 수도 있다.
다익스트라: 시작점으로부터 나머지 정점까지의 최단경로를 구할 때 사용

시간복잡도
BFS탐색: E
다익스트라: ElogV(인접리스트+우선순위 큐)

최단거리를 구하고자 할 때,
사용전략
간선들 길이가 작을 때 다익스트라 알고리즘 대신에 BFS탐색을 이용해 최단 거리를 구할지 고려하자.
BFS는 모든 간선이 단위 길이로 이루어졌을때 방문하는 시점마다 해당 정점의 최단 경로를 구할 수 있기 때문에 다익스트라 알고리즘보다 빠른 경우가 있다.

즉, 주어진 간선들을 단위 길이의 간선으로 쪼개서 정점을 만든 후에 BFS탐색을 돌면 모든 정점들의 최단경로를 구할 수 있다.
0 Comments
댓글쓰기 폼