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