[알고리즘/그래프] 크루스칼(Kruskal) 최소 신장 트리 vs 다익스트라(Dijksta) 최단 경로

그리디 알고리즘 과정

1. 해 선택
2. 실행 가능성 검사
3. 해 검사

 

크루스칼(Kruskal)과 그리디 알고리즘 

최소 신장트리는 사이클을 형성하지 않고 그래프 내의 모든 정점을 최소의 비용으로 연결하는 트리이다. 최소 신장 트리를 구축하는데 한 가지 중요한 제약은 최소 신장 트리 내에 사이클이 형성되어서는 안된다는 것이다. 

 

크루스칼 알고리즘 동작 방식

1) 그래프 내의 모든 간선의 가중치에 대해 오름차순으로 정렬한다.

2) 1)의 간선을 차례대로 순회하면서 최소 신장 트리에 추가한다. (사이클 생성 x)

그리디 과정으로 다시 보면 다음과 같다.

1.    해 선택 : 가장 작은 가중치의 간선 선택
2.    실행 가능성 검사 : 사이클 생성 여부 파악 (사이클 생성되면 x)
3.    해 검사 : 모든 정점이 하나의 집합에 있는지 확인 

 

다익스트라(Dijkstra)와 그리디 알고리즘 

다익스트라 최단 경로 알고리즘은 그래프 내의 한 정점에서 다른 정점으로 가는 최단 경로를 구하는 알고리즘이다.

 

다익스트라 알고리즘 동작 방식

1. 각 정점 위 시작점으로부터 자신에게 이르는 경로의 비용을 최댓값으로 설정 (초기값 Integer.MAX_VALUE)
2. 시작 정점의 경로 길이를 0으로 초기화하고 최단 경로에 추가 (dp[start] =0; q.add(new Node(start,0);)
3. 큐에 들어있는 정점의 인접 정점들에 대한 경로 길이를 갱신하고 이들을 최단 경로에 추가
   1. 만약 추가하려는 인접 정점이 이미 최단 경로 안에 존재한다면 갱신되기 이전의 경로 길이가 새로운 경로의 길이보다 더 큰 경우 기존 경로를 현재 정점을 경유하게 값 갱신
4.  그래프 내의 모든 정점이 최단 경로에 소속될 때까지 3) 을 반복함

 

그리디 과정으로 다시 보면 다음과 같다.

1. 해 선택 : 주어진 시작점을 선택 , 3번과정 반복
2. 실행 가능성 : 이전의 경로 길이가 새로운 경로의 길이보다 더 큰 경우 기존 경로를 현재 정점을 경유하게 값 갱신
3. 해 검사 : 4번 과정에서 해 검사를 맡고 있음

 

표로 비교해보기

	다익스트라 (Dijkstra)	크루스칼 (Kruskal)
구현 방법	우선순위 큐 + dp(점화식)	우선순위 큐 + union-find(서로소집합)
중심	정점	간선
시작점	출발점이 정해져 있는 경우	간선의 가중치가 작은 것부터 시작(오름차순 정렬)
Queue 진입시점	dp갱신될 때만 (최단경로 갱신) 그 정점에서 출발하는 간선을 우선순위 큐에 추가	모든 정점을 우선순위 큐에 넣고 시작
용도	한 정점에서 다른 정점의 최단 거리를 구하는 경우	최소 신장 트리를 그릴 때
최단 거리	임의의 두 점 간의 최단 거리 구할 때 사용	최소의 비용(최단거리) 모든 점을 다 연결할 때 사용. 모든 점을 다 이은 경로가 최단 거리라고 말할 수 있지만 임의의 두 점 간의 거리가 최단 거리라는 보장은 없다.

 

---

각 자세한 설명은 아래 링크에서 참고

최소 신장트리 : 크루스칼(Kruskal) 알고리즘

[알고리즘/ 그래프] 최소 스패닝 트리 - 크루스칼(Kruskal)과 프림(Prim) 알고리즘 (Java)

 

최단 경로 : 다익스트라(Dijkstra) 알고리즘

[알고리즘] 그래프 다익스트라(Dijkstra) vs 플로이드 와샬(Floyd Warshall) [JAVA]