다익스트라, MST, Floyd-Warshal

Dijkstra

• 최단거리 알고리즘
• 간선에 가중치가 있는 경우 사용
• 지속적으로 거리를 갱신
• 정점의 수 : V, 간선의 수 : E
  • 인접 리스트 + 힙 사용시 : O(ElogV)

MST

Spanning tree

• 그래프 내 모든 정점을 포함하는 트리
• 최소 연결이어야 한다.(최소 간선)
  • n개의 정점을 가진 경우 n-1개의 간선을 가지게 된다.

MST

Spanning tree 중 간선들의 가중치 합이 최소인 트리

Kruskal MST

• Greedy를 이용하는 법
  • 사이클을 이루지 않는 최소 간선을 선택한다.
• union find 사용
  • 선택한 간선을 통해 연결하려는 두 정점이 이미 같은 그룹에 있지 않는지 확인할 때 사용
• Kruskal 참고

Prim MST

• 시작 정점에서부터 출발하여 신장트리 집합을 단계적으로 확장해나가는 방식
• 정점 선택을 기반으로 하고 있다.
  • 인접한 정점들 중에서 최소 간선으로 연결된 정점을 선택하여 트리를 확장한다.
  • 이러한 과정을 n-1개의 간선을 가질 때까지 반복한다.
• Prim 참고

Floyd-Warshal

• 모든 정점간 최소 경로를 구할 수 있다.
• 2차원 입접행렬을 이용하여 더 작은 값을 가지도록 갱신
• 시간 복잡도 O(n^3)