MST와 최단 경로

MST의 정의는 사이클이 존재하지 않으면서 그래프의 모든 정점을 연결한 그래프를 의미한다. 이때, 간선의 가중치는 최소가 된다. 그리고 MST는 다양하게 생길 수 있다

 

예를 들어 4개의 정점이 있고, 4개의 정점에 대한 최단경로를 구하려고 한다면?

MST를 생각할 수 있지만, 실제로는 그렇게 되지 않는다. 왜냐하면, 실제 방문한 정점을 다시 방문하면서 돌아가는 것이 더 빠를 수 있기 때문이다. 하지만 MST는 한 번 방문한 정점은 거치지 않기 때문에 매번 최단경로라고 답을 내지 않는다