[TIL] 그래프의 최소 비용 문제

그래프의 최소 비용 문제

가중치 그래프에서 최소 비용 문제에는 대표적으로 두 가지 문제가 출제된다.
첫번째는 모든 정점들을 연결하는 간선들의 가중치 합이 최소가 되는 최소 신장 트리 문제,
두번째는 시작 정점에서 목표 정점까지 가는 간선의 가중치 합이 최소가 되는 최단 경로 문제이다.

1.최소 신장 트리(Minimum Spanning Tree, MST)

신장 트리(Spanning Tree)란 n개의 정점을 포함하는 무향 그래프에서 n개의 정점과 n-1개의 간선으로 구성된 트리이다.
최소 신장 트리는 가중치 그래프의 신장 트리 중에서 간선들의 가중치 합이 최소인 신장 트리를 의미한다.
MST를 찾는 대표적인 알고리즘은 프림(Prim) 알고리즘과 크루스칼(Kruskal) 알고리즘이 존재한다.

Prim 알고리즘
한 정점에 연결된 간선들 중하나씩 선택하면서 최소 신장 트리를 만들어가는 알고리즘이다.
알고리즘의 구성은 아래와 같다.

1. 임의의 정점을 하나 선택해서 시작한다.(일반적으로 0번)
2. 해당 정점과 인접한 정점 중 가장 가까운 정점을 하나 선택한다.
3. 선택된 정점과 가장 가까운 정점을 고르는 것을 반복한다.
   프림 알고리즘을 위해서는 연결된 정점과 연결되지 않은 정점에 대한 정보가 있어야한다.

Kruskal 알고리즘
최소 가중치 간선을 하나씩 선택해서 최소 신장 트리를 찾는 알고리즘이다.
최고 모든 간선을 가중치에 따라 오름차순으로 정렬하고, 가중치가 낮은 간선터 선택하여 트리를 확장한다.
최서 가중치 간선의 선택을 반복한다.

1. 모든 정점에 대해 자기 자신을 부모로 한다.
2. 모든 간선을 가중치에 따라 정렬한다.
3. 간선을 하나씩 선택하며 다른 집합이면 MST에 추가하고 집합을 합친다.(union, find)
   같은 집합에 속하는 간선일 경우 넘어간다.
4. root의 랭크가 같으면 둘 중 하나의 랭크를 높인다.
   (이는 자신에 속하는 서브 트리의 높이이다.)

2.최단 경로

최단 경로란 간선의 가중치가 있는 유향 그래프에서 두 정점 사이의 경로들 중 간선의 가중치의 합이 최소인 경로이다.
대표적인 알고리즘은 단일 시작점인 경우 다익스트라(Dijkstra)와 벨만-포드(Bellman-Ford)알고리즘이 있다.
모든 쌍 최단 경로 문제는 플로이드-워셜(Floyd-Warshall) 알고리즘을 이용한다.

Dijkstra 알고리즘
시작 정점에서 거리가 최소인 정점부터 선택해 나가면서 최단 경로를 구하는 방식이다.
Prim 알고리즘과 유사한 탐욕 기법 알고리즘으로, 시작 정점(r)에서 끝 정점(t)까지의 최단 경로에
정점 x가 존재하면 최단 경로는 r에서 x까지의 최단 경로와 x에서 t까지의 최단 경로로 구성된다.

1. 시작점에서의 최단 경로를 찾은 정점과 찾지 못한 정점으로 분리한다.
2. 최단 경로를 찾은 정점을 하나씩 집합에 추가하며 진행한다.
   다익스트라 알고리즘은 한 번 집합에 포함된 정점에 대해서는 갱신하지 않기 때문에 음의 가중치는 반영할 수 없다.
   

Bellman-Ford 알고리즘
음의 사이클이 아닌 음의 가중치를 포함하는 그래프에서 사용할 수 있는 알고리즘이다.
출발점에서 각 정점까지 간선 하나로 구성된 경로만 고려해서 최단 경로를 구한다.
DP가 적용된 알고리즘으로, 다익스트라에 비해 많은 시간이 소요된다.