[알고리즘 정리] 최소 신장 트리(MST, Minumum Spanning Tree) 알고리즘(프림 알고리즘)

최소 신장 트리와 다익스트라 알고리즘 차이

• 우선 최소 신장트리에는 프림 알고리즘, 크루스칼 알고리즘 2가지 방법이 있지만 여기서는 프림 알고리즘에 대해서 알아본다.
  (보통 하나의 알고리즘만 알더라도 대부분의 경우 해결이 되었다.)
• 다익스트라 알고리즘의 경우 한 노드에서 다른 노드까지 가장 작은 가중치를 가지는 경로 입니다.
• 최소 신장 트리는 각 노드들의 가중치가 가장 작은 상태로 모든 vertex(node)를 연결하는 경로 입니다.
• 밑에 과정을 보시면서 가장 중요한 다른 부분은 Update하는 순간 입니다.
      - 다익스트라의 경우 A로 부터 해당 노드까지의 경로가 더 작아지는 순간에 Update 하는 반면
      - 최소 신장 트리의 경우 새로 발견된 Edge의 가중치가 기존의 가중치보다 작은 경우 Update 하게됩니다.
  
• 결론적으로 다익스트라의 경우 A에서 부터 B까지의 경로는 A->B 이며, 최소 신장 트리의 경우 A -> D -> C -> B 이다.
  

다익스트라 알고리즘

최소 신장 트리 알고리즘

최소 신장 트리 단계

• 여러 노드 중 어느 노드를 선택해도 동일한 결과가 나온다.(밑에 예시에서는 A부터 시작한다.) -> 귀납법으로 증명 할 수 있다.
• Update의 경우 새로 발견된 가중치가 기존의 가중치 보다 작으면 바로 바꾸게 된다.