알고리즘 - 최소 신장 트리, 최단 거리 알고리즘

최소 신장 트리(MST, Minimum Spanning Tree) 가중치가 있는 그래프에서 간선의 가중치 총합이 가장 작은 신장 트리

*신장 트리: 그래프의 모든 정점을 포함하는 트리 

 

① 프림 알고리즘 

그리디 알고리즘으로 임의의 정점을 시작점으로 트리를 확장하면서 최소 신장 트리를 생성하는 방식 

방문 가능한 정점 중 비용이 적게 드는 정점을 선택해 트리 확장 

 

② 크루스칼 알고리즘

여러 트리를 합쳐 하나의 최소 신장 트리를 생성하는 방식

간선을 가중치에 따라 정렬한 . 뒤낮은 가중치를 갖는 간선을 선택하며 여러 트리를 하나로 합쳐 나감

 

 

 

최단거리 알고리즘

1. 그래프의 특정 정점에서 다른 정점까지의 최단 거리를 구하는 알고리즘
2. 다익스트라 알고리즘
   • 간선의 가중치가 음수가 아닌 경우 최단 거리를 구하는 알고리즘
   • 방문 가능한 정점 중 비용이 가장 적은 정점을 방문 
   • 방문한 정점과 연결된 다른 정점의 비용 생신이 가능한 경우 갱신 수행
3. 벨만-포드 알고리즘
   • 간선의 가중치가 음수인 경우까지 최단 거리를 구하는 알고리즘 
   • 음의 사이클이 있으면 알고리즘을 적용할 수 없음