[자료구조] 1117

11. 그래프(2)

1. 최소 비용 신장 트리 (MST: Minimum Spanning Tree)
2. Kruscal의 MST 알고리즘
3. Prim의 MST 알고리즘
4. 최단 경로
5. Dijkstra의 최단 경로 알고리즘
6. Floyd의 최단 경로 알고리즘
7. 위상 정렬

 

---

11.3 Prim의 MST 알고리즘

Prim's MST 프로그램

 

▶ Disconnected Graph:

• Kruskal's MST algorithm: 전체 edge의 weight를 비교하여, edge weight가 작은 것부터 연결하기 때문에, disconnected graph도 처리할 수 있다.
• Prim's MST algorithm: 이미 MST에 포함된 vertex와 연결된 edge들의 weight만을 비교하기 때문에, disconnected graph에서는 제대로 동작하지 않는다.

Prim's MST 프로그램

 

 

Prim's MST 프로그램 vs. Kruskal's MST 프로그램

Prim's MST 프로그램 vs. Kruskal's MST 프로그램

• 모든 간선들의 weight가 다르고, connected graph라면, MST의 결과는 동일하다.
• 하지만 간선들이 추가되는 순서는 다르다.

 

 

Prim's MST 알고리즘 vs. Kruskal's MST 알고리즘

• Kruskal's MST 알고리즘 --> O(e log (e))
  : 모든 edge들의 weight를 한번에 비교한다. --> 희박한 그래프에서 유리하다.
• Prim's MST 알고리즘 --> O(n^2)
  : 이미 MST에 포함된 vertex와 연결된 edge들의 weight만을 비교한다. --> 밀집한 그래프에서 유리하다.

Prim's MST 알고리즘 vs. Kruskal's MST 알고리즘

 

Prim's MST - Example

Prim's MST - Example

 

Kruskal's MST - Example

Kruskal's MST - Example

 

---

11.4 최단 경로(shortest path)

: 시작정점과 도착정점을 연결하는 경로중에서, edge들의 weight 합이 최소가 되는 경로

최단 경로(shortest path)

 

가중치 인접행렬

가중치 인접행렬

 

최단 경로 알고리즘

• Dijkstra 알고리즘: 하나의 시작 정점에서 다른 정점까지의 최단경로 계산
• Floyd 알고리즘: 모든 정점에서 다른 모든 정점까지의 최단경로 계산

 

---

11.5 Dijkstra's 최단 경로 알고리즘

Dijkstra's 핵심 아이디어

• distance 배열: 최단경로가 알려진 정점들만을 이용한 다른 정점들까지의 최단경로 길이
  **최단경로 길이: sum --> 도착지까지 가는 경로에 포함된 모든 edge들의 weight의 합
• 집합 S: 시작정점 v로부터 최단경로가 이미 알려진 정점들의 집합

--> 매 단계에서 가장 distance 값이 작은 정점을 S에 추가한다. ("이 정점부터 연결해야 shortest path야!")

 

Dijkstra's 알고리즘: distance 값 갱신

Dijkstra's 알고리즘: distance 값 갱신

 

 

Dijkstra's 알고리즘 증명

Dijkstra's 알고리즘 증명

 

 

Dijkstra's 최단 경로 알고리즘

Dijkstra's 최단 경로 알고리즘

예) 집합 S에 정점u가 새롭게 추가되었다. u에 인접한 정점z가 있다. 시작정점 v부터 z까지의 거리보다 (v-->u-->z)가 더 가깝다.

=> distance[z] = v --> u --> z

 

Dijkstra's 최단 경로 알고리즘 - Example

 

Dijkstra's 최단 경로 알고리즘 - Example

: 집합 S에 새로운 정점이 추가될 때마다, 그 정점과 인접한 정점까지의 distance가 업데이트될 가능성이 생긴다.

 

---

 

 

 

 

 

출처: 이화여자대학교 이숙영교수님 자료구조