Point 💡

그래프 최단경로?

그래프의 최소합, 최단경로 문제가 나오면, 필자는 BFS(**Breadth-First Search)**를 생각한다. 그러나 어떨 때는 BFS, 어떨 때는 다익스트라.. 제각각이다. 따라서 필자는 어떤 경우에 각 알고리즘을 적용시킬 수 있는지 알아보기로 했다.

BFS의 한계

가중치가 없는 그래프의 최단경로를 찾는 경우에는 우리는 자주 BFS를 사용하여 알고리즘을 푸는 것을 확인할 수 있다. 그러나, 각 간선의 가중치가 다를 때도 BFS를 사용할 수 있을까? 다음 그림을 확인하자.

BFS로는 0번 정점에서 2번 정점으로 가는 최단거리를 찾을 수 없다. 우리 눈으로는 0→1→3→2 순서로 최단 경로를 찾을 수 있지만, BFS가 방문하는 순서는 0→(1,2번 정점 방문)→3 이기 때문에, BFS로는 해결할 수 없는 것이 확실하다.

다익스트라 알고리즘

이런 상황에서 쓸 수 있는 것은 다익스트라 알고리즘이다. 그러나 그래프의 간선의 가중치에 음수가 있을 경우, 특히 음수 사이클이 있을 경우, 다익스트라 알고리즘이 제대로 동작하지않는다. ****이 경우는 벨만-포드 알고리즘을 사용해야한다.

BFS는 방문한 순서대로 정점들을 방문하기 때문에, 거리가 더 짧은 간선이 발견되어도 큐에서 “새치기”할 수 없다. 하지만, 위 상황 속에서 우리는 간선이 좀 더 늦게 발견되어도 큐에서 “새치기”를 할 수 없다. 하지만, 위 상황 속에서 우리는 간선이 좀 더 늦게 발견되어도, 길이(가중치)가 짧다면 발견된 순서를 무시하고, “새치기”를 할 필요가 있음을 알 수 있다.

그렇다면, “새치기”를 할 수 있는 큐를 도입해서, BFS를 한다면 위의 문제를 해결할 수 있지않을까? 이러한 아이디어에서 시작하는 알고리즘이, 우선순위 큐를 사용하는 다익스트라 알고리즘이다.

BFS에서는 생기지 않는 상황이 다익스트라 알고리즘에서는 발생한다.

위의 그림으로 표현하자면, 시작점을 방문하고 나서는 (1,2), (2,12)가 우선순위 큐 내에 들어간다. 계속해서 탐색을 하다보면 (2,9) 또한 들어간다. dist[]는 올바르게 갱신되지만, 이미 큐 속에 들어가있는 (2,12)를 어떻게 하는게 좋을까? ****간단한 방법은 (2,9)를 꺼내서 연산을 수행하고, (2,12)가 꺼내 졌을때 이를 무시하는 것이다.