Greedy - Shortest Path

목표 : 최단경로 찾기

---

Dijkstra

• RedSet 은 최적합이 결정된 노드 집합
• BlueSet 은 결정되지 않은 노드 집합

 

---

 

알고리즘

1. 소스를 RedSet에 넣어서 시작한다.
2. BlueSet 중에 가장 작은 웨이트 노드(u)를 RedSet에 넣는다.
3. BlueSet의 노드 웨이트들을 (기존 노드w의 웨이트)와 (u 노드 웨이트 + u→w 의 웨이트)를 비교하여 더 작은 값으로 갱신한다.
4. 2 - 3을 반복한다.

 

---

Prim을 Dijkstra로 변경하기

1) Prim에서 웨이트는 현재 Tree set에 인접 노드 중 가장 작은 웨이트 (엣지)이다.
2) Dijkstra에서 웨이트는 소스로부터 타겟 노드까지의 경로들 중 가장 작은 웨이트 최적 합이다.

Prim 은 Priority Queue 를 통해서 구현 가능하다.
소스부터 시작해서 연결된 노드들을 PQ에 넣고 빼가며
노드를 서로 잇는 가장 작은 엣지 웨이트들을 결정해 나간다.
그러므로 PQ 내부로 들어가서 정렬되는 기준은 엣지 웨이트이다.

다익스트라는
1. blueset 중 가장 작은 웨이트의 노드(u)를 redset에 추가
2. blueset의 노드(w)와 u + u→w 엣지의 웨이트를 비교하여 작은 값으로 갱신 하는 과정을 반복하므로

PQ의 정렬 기준을 엣지 웨이트가 아니라 소스로부터의 웨이트 최적 합으로 바꿔주면 된다.

즉, redset에 들어간 노드(u)의 웨이트 + u → w를 잇는 엣지 웨이트로 변경해 준다면
PQ 내부에서 기존 w와,u + u→w를 크기로 정렬할 것이기 때문에 Dijkstra를 구현할 수 있다.

---

1753번: 최단경로

1916번: 최소비용 구하기