그래프 - 최단거리 [BFS vs Dijkstra(다익스트라)]

Dijkstra는 BFS 기반으로 만들어진 최단거리 알고리즘입니다. 하지만 때로는 가장 빠른 길을 구할 때 BFS도 사용하기 때문에 비교해보았습니다.

BFS

모든 Edge의 가중치가 같을 때 사용되며 Queue에 들어가는 순서(혹은 나오는 순서)대로 짧은 순입니다.

Dijkstra

Edge마다 가중치가 다를 때 사용됩니다. Queue에 들어가는 순서와 상관이 없습니다. 그래서 Queue를 사용하지 않고 가중치만 저장했다가 가중치가 가장 적은 노드를 선택하기도 합니다. 혹은 Priority Queue 를 사용해서 노드와 함께 가중된 거리를 함께 넣어주었다가 가중치가 가장 적은 노드를 선택해서 꺼내 쓸 수 있습니다. Priority Queue를 사용하면 훨씬 빠르게 찾을 수 있습니다. 단 음수 가중치는 사용할 수 없습니다.