최단거리(다익스트라) vs 최소 신장 트리(크루스칼)

정리

	다익스트라	크루스칼
용도	일대다 정점 간의 최소 거리 파악	최소 신장 트리(MST) 파악
중심	정점(Node)	간선(Edge)
모든 정점 방문	X	O
구현 방법	우선 순위 큐 + dist[점화식]	우선 순위 큐 + Union-Find
시작점	출발점이 정해져 있는 경우	간선 가중치가 작은 것부터
큐에 넣는 시점	dist가 갱신 될 때 그 점에서 출발하는 간선을 큐에 넣음	모든 정점을 우선순위 큐에 넣고 시작
끝	점과 점 사이의 최단 거리를 찾고 나면 더이상 탐색하지 않음	최소신장 트리가 만들어 질 때까지 탐색
최소	임의의 두 점 간의 최소 거리를 구할 때 사용	최소 비용으로 모든 점을 다 이을 때 사용 임의의 두 점 간의거리 최소 보장 X

 

최단거리 알고리즘

그래프 최단거리 알고리즘 정리 및 비교 (다익스트라, 벨만-포드, 플로이드-워셜)

 

최소 신장 트리 알고리즘

[1197번] 최소 신장 트리(MST, 크루스칼, 프림, 유니온파인드)