최소신장트리 다익스트라 - choesosinjangteuli daigseuteula

그리디 알고리즘 과정

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번 과정에서 해 검사를 맡고 있음

표로 비교해보기

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

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

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

스패닝 트리 또는 신장 트리 어떤 무향 그래프의 스패닝 트리는 원래 그래프의 정점 전부와 간선의 부분 집합으로 구성된 부분 그래프이다. 이때 스패닝 트리에 포함된 간선들은 정점들을 트리

loosie.tistory.com

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

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

Dijkstra 알고리즘은 하나의 정점에서 출발했을 때 다른 모든 정점으로의 최단 경로를 구하는 알고리즘이다. 그에 반해 Floyd Warshall 알고리즘은 모든 정점에서 모든 정점으로의 최단 경로를 구하는

loosie.tistory.com

'Dot Algo∙ DS > 알고리즘 개념' 카테고리의 다른 글

티스토리 뷰

최소 신장 트리와 다익스트라 알고리즘 차이

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

최소 신장 트리 단계

• 여러 노드 중 어느 노드를 선택해도 동일한 결과가 나온다.(밑에 예시에서는 A부터 시작한다.) -> 귀납법으로 증명 할 수 있다.
• Update의 경우 새로 발견된 가중치가 기존의 가중치 보다 작으면 바로 바꾸게 된다.