다익스트라와 최소 스패닝 트리

다익스트라와 최소 스패닝 트리의 차이

백준 2211번 네트워크 복구 문제를 고민하다가 너무 헷갈려 따로 정리해두고자 한다.

처음엔 최소 스패닝 트리 관련 문제로 해석하여 다짜고짜 비용비싼 간선들 다 버리면서 네트워크 복구시켜놨더니 오답폭탄을 맞았다.

그럴리가 없다며 디버깅만 며칠이 이어졌다. 무지성 돌격

참다참다 분류표 확인하니 다익스트라 이더라.

🥲

얼핏 비슷한 듯 다른 두 알고리즘의 차이를 확인해보자.

다익스트라와 최소 스패닝 트리의 특징

다음과 같은 특징을 갖는다.

다익스트라

• 두 접점사이의 최소거리를 구하는 알고리즘
• 우선순위 큐, 점화식을 이용

최소 스패닝 트리

• 스패닝 트리를 만들되, 최소 비용으로 구성한다.
• 대표적인 알고리즘으로 크루스칼, 프림 등이 있다.
• 프림의 경우, 접점을 기준으로 알고리즘 동작
• 크루스칼의 경우, 간선을 기준으로 알고리즘 동작

스패닝 트리를 만족한다는 것은, 모든 접점들이 서로 연결이 되어있다는 것이다. 이때 하나의 이어지는 접점에서 중복이 존재해서는 안된다.

한붓 그리기를 연상하면 편하다.

차이점

비슷한 듯 다른 두 알고리즘. 제일 헷갈리게 하는 부분은 둘다 최소비용을 구하기 위해 사용되는 알고리즘 이라는 것이다.

우리는 여기서 다음의 특징적 차이점에 주목해보도록 하자. 바로

다익스트라는 두 접점사이의 최소비용을 구하는 알고리즘 이며,

최소 스패닝 트리는 스패닝트리를 구성하되 구성하는 간선의 비용이 최소가 되어야 한다는 점이다.

말로 하는건 여전히 어렵다. 그림으로 알아보자.

다음과 같은 그래프를 확인해보자.

다익스트라를 이용하여 접점간의 최소 이동거리를 구하면 어떻게 될까?
(1번 접점부터 시작한다고 가정하자.)

다음과 같이 진행 될 것이다.

그렇다면, 주어진 그래프에서 최소 스패닝 트리를 구하면 어떻게 될까?

물론 위의 다익스트라 과정에서 채택된 간선들 또한 최소 스패닝 트리를 만족한다.
그러나, 다음의 경우도 있다는 것을 알아두자.

바로 가중치가 2인 간선을 ① 과 ③을 연결하는 간선을 채택하는 것이 아니라, ② 와 ③을 연결하는 간선을 채택하는 것이다.

위의 경우에도 최소 스패닝 트리를 만족하는 것을 확인할 수 있다.

그러나 ①에서 ③으로 이동하는 비용이 2에서 3으로 증가했다는 것을 알 수 있다.

이러한 이유 때문에 백준 문제에서 최소스패닝트리가 아닌 다익스트라로 문제를 해결해야 했던 이유이다.

다익스트라는 최소 스패닝 트리를 보장하지 못한다.

결론

다익스트라는 최소 스패닝 트리를 보장하지 못하며,

최소 스패닝 트리를 구했다 하더라도 접점간의 최소 거리를 보장하지 못한다.

상당히 오랜시간 고민했던 건데 정리하고 보니까 명확해지는 것 같다.

시간적 여유가 되면 알고리즘을 소개하는 글들 도 여럿 작성해보도록 하겠다.
된다면 말이다