[그래프 알고리즘] 다익스트라와 크루스칼의 차이

평소에 다양한 그래프 알고리즘을 알고 있는데, 어느 순간 무슨 차이가 있지라는 생각이 들며 헷갈리기 시작했다.

특히 크루스칼, 프림 알고리즘은 MST(최소 스패닝 트리)의 일종이고, 다익스트라는 하나의 정점에서 다른 모든 정점(일대다)로의 최단 경로를 위한 알고리즘임은 이론상 알고 있으나, 응용할 때 어떤 알고리즘을 써야할지 난감했다.

 

그래서 서치한 결과 찾은 차이점 정리!

 

	다익스트라	크루스칼
구현 방법	우선순위 큐 + dist[점화식]	우선순위 큐 + Union-Find
중심	정점(Node) 중심	간선(Edge) 중심
시작점	출발점이 정해져 있는 경우	간선이 가중치가 작은 것부터 시작
용도	일대다 정점 간의 최소 거리 파악	최소 신장 트리(MST) 파악
모든 정점 방문	정점 중심이므로 모든 정점의 끝까지 안 갈 수도 있다.	간선 중심이므로 모든 정점을 방문하며 끝까지 그려야 한다.
최소의 의미	임의의 두 점 간의 최소 거리 파악	최소 비용으로 모든 정점을 잇기 임의의 두 점 간의 거리가 최소인 거는 보장 X

 

다익스트라 알고리즘

1. 초기화

✔︎ 시작점의 dist를 0으로 설정

2. 갱신

✔︎ 우선순위 큐에서 간선 정보(노드 인덱스, 거리)을 꺼내와서 그 간선을 썼을 때 최소 dist를 갱신하는지 확인

 

✔︎ 갱신가능하면 갱신

 

✔︎ 그 점과 이어진 간선을 지금까지의 가중치 + 해당 간선의 가중치로 만든 다음 우선순위 큐에 다시 삽입

 

이렇게 다익스트라를 끝까지 돌린다고 MST가 나오는 것은 아니다.

크루스칼 알고리즘

1. 우선순위 큐에 모든 간선을 넣는다.

2. 우선순위 큐에서 가중치가 작은 순서대로 간선을 꺼낸다.

3. 해당 간선을 추가했을 때 사이클이 생기는지 여부를 확인한다.(Union-Find)

4. 사이클이 생기지 않는 경우 해당 간선을 추가하고 가중치를 더해간다.

5. pq를 다 돌거나 Union이 true인 횟수가 V-1이 되면 MST 완성

 

참고

https://buddev.tistory.com/21

다익스트라 vs 크루스칼 비교 (java)