BFS는 왜 가중치가 있는 그래프에서 사용할 수 없을까?

BFS는 가중치가 있는 간선이 있는 그래프에서는 최단 거리 알고리즘으로써 사용될 수 없다.

 

그 이유는 BFS는 방문한 순서대로 동작을 하게 되기 때문이다.

 

그렇기 때문에 다음과 같은 상황에서 전혀 사용할 수 없는 것이다.

 

시작점이 A라고 가정해보자. 시작점 A를 방문하게 되었을 때 BFS 알고리즘을 이용하게 된다면 (2, B)와 (12, C)를 '그냥 큐'에 넣게 될 것이다. 그리고 나서 D를 방문하게 되고 알고리즘은 종료를 하게 될 것이다.

 

이렇게 될 경우 BFS 알고리즘 입장에서 A에서 C까지의 최단 경로가 12가 되는 것이다. 실제로는 2 + 4 + 3 = 9 인데도 말이다.

 

즉, A에서 C까지의 최단 경로는 A to C가 아니라 A to B to D to C가 되는 것이다.

 

이러한 상황에서 BFS 알고리즘은 의미가 없어지게 되고 이를 해결하기 위해 나온 알고리즘이 대표적으로 다익스트라 알고리즘이 있다.