Algorithm 11 - MST

 Minimum Spanning Tree(MST)

spanning tree : 그래프의 모든 노드를 연결하면서 사이클이 존재하지 않는 트리. 따라서 n개의 노드에 대해 n-1개의 edge를 가진다.
각 edge에 weight(일반적으로 거리)를 줄 때 spanning tree의 edge weight의 합이 최소가 되는 트리를 MST라 한다. 단, 같은 최소값을 가지는 여러 개의 MST가 존재할 수도 있다. (MST is not unique)

이를 만드는 방법은 반드시 포함될 safe edge를 차례로 선택해 가는 것이다.
safe edge : MST의 edge set A에 해당 edge를 추가해도 optimal solution에 포함되는 edge.  따라서 A는 항상 MST인 optimal solution의 subset이어야 한다.

전체 그래프에서 edge (u,v)의 코스트가 가장 적고, u는 subset S에, v는 subset V-S에 포함되어 있다면 어짜피 spanning tree는 모든 노드를 연결해야 하므로 S와 V-S를 연결해야 한다. 그리고 (u,v)의 코스트가 제일 적으면서 이들을 연결하고 있으므로 이들을 선택해야 MST가 될 수 있다.

- cut : graph를 S와 V-S로 분리하는 것. 모든 노드들은 둘 중 하나에만 속하게 된다.
- crosses : cut을 가로지르는 edge
- respects : 어떤 set의 모든 edge들이 cut을 가로지르지 않는다면, 해당 set을 주어진 cut이 respect 한다고 한다.
- light edge : cut을 가로지르는 crossing edge 중에 가장 적은 weight를 가지는 edge.
그래프의 노드들은 적어도 하나의 다른 노드들과 연결되어 있고, cut은 이들을 가로지르므로 반드시 하나 이상의 crossing edge가 생긴다. 따라서 그들 중 가장 적은 weight을 가지는 것이 light edge가 된다.

MST : Theorem 1
MST를 형성중인 minimum cost edge의 set A에 대해, A를 respect하는 cut으로 그래프가 분리된 상태를 고려하자. 해당 cut으로 분리된 S와 V-S 의 light edge는 A에 추가해도 되는 safe edge이다. (왜냐하면 앞서 설명한 것 처럼 분리된 두 개의 sub tree는 어짜피 연결되어야 하고, MST를 형성하기 위해서는 이들을 연결하며 최소 값을 가지는 edge를 선택해야 하기 때문)

MST : Corollary 2
상기의 vertex level theorem을 트리끼리 형성한 forest에도 적용 가능.

- Kruskal's algorithm
edge를 weight 순으로 sort하여 낮은 것부터 선택해가며 merge해가는 방식. 단, 이 때 선택한 edge가 이미 연결한 두 노드를 연결하고 있지는 않는지, 혹은 사이클을 형성하지 않는지 확인해야 한다. 이를 위해 disjoint set data structure를 사용할 수 있다.

따라서 전체 edge를 cost가 낮은 것부터 하나씩 확인하여 조건에 맞다면 연결(MST set A에 포함) 아니면 다음 낮은 cost를 가지는 edge로 이동하는 방식으로 MST를 형성한다.
이는 sub tree를 만들어가며 매 단계마다 이들을 연결하는 것으로 생각할 수 있다.(각 노드도 트리로 생각)




- Prim's algorithm
상기방법과는 달리 하나의 single tree를 만들게 된다.이는 하나의 root를 선택하고, 매 단계마다 가능한 가장 낮은 cost를 가지는 edge를 선택하여 MST를 만드는 방식이다. 따라서 root를 어디로 선택하느냐에 따라 달라질 수 있다.
따라서 BFS와 DFS의 관점에서 생각해보면, kruskal은 BFS의 아이디어와 비슷하고, prim은 DFS와 비슷하다는 것을 알 수 있다.


Shortest-path problem
weight가 두 vertex의 사이의 거리로 주어져 가장 작은 weight를 가지는 path를 찾는 문제. 이 때 각 path의 거리에 따라 최소 거리인 경로가 여러개 존재할 수 있다.

single-source shortest path : weight가 음수인 cycle이 source에서 갈 수 있는 곳에 존재하지 않는다면, 이를 정의할 수 있다.

shortest path의 subset 역시 shortest path이다. 왜냐하면 가장 긴 경로를 이루는 각 vertex 끼리의 경로도 최소가 되어야 전체가 최소가 될 수 있기 때문이다. 이를 통해 어떤 두 노드 사이의 shortest path는 sub path에서 부터 확장하여 얻어낼 수 있다.

predecessor subgraph : shortest-path tree
shortest path weight와 해당 shortest path의 vertices를 나타내기 위한 트리로 각 vertex는 shortest-path estimate v.d와 predecessor v.pi 를 가지고 있다. 이 때 estimate가 최소와 같아지면 이는 shortest가 되고, v.pi는 predecessor로 각 path에서 해당 노드의 직전 노드를 가리킨다.
이를 통해 source 노드에서 모든 노드까지의 shortest path 경로와 거리를 알 수 있다.

Relaxation
만약 a->c보다 a->b->c를 거쳐서 가는 경로가 더 짧다면 이를 shortest path로 선정해야 한다. 따라서 shortest path estimate에 다른 경로를 relaxation하여 만약 다른 곳을 거쳐 가는 경로가 더 짧다면 이를 shortest path estimate 로 선정한다. 만약 그렇지 않다면 기존 값을 그대로 선정한다.
이 과정을 relaxation이라 한다. 이를 반복적으로 수행하여 최종 shortest path를 찾을 수 있다.

shortest path property
- triangle inequality : 삼각형 두 변의 합은 항상 나머지 한 변보다 커야 하는 것 처럼, 여기서도 만약 최소 경로라면 다른 곳을 거쳐서 갈 때 최소 경로보다 항상 크거나 같아야 한다.
- upper bound property : estimate는 항상 최적보다 크거나 같고, relaxation을 통해 최적 값을 얻어내면 더 이상 바뀌지 않는다.
- path relaxation property : 어떤 경로가 최소 경로 일 때 이를 relaxation 하면 해당 소스 노드에서 해당 노드 까지의 거리가 v.d 가 된다.

Dijkstra's algorithm
source node로 부터 가장 가까이 있는 vertex를 선택하는 greedy approach. 그러나 모든 edge가 non-negative여야 올바르게 작동한다.
이는 priority queue를 이용하여 거리를 기준으로 정렬한 뒤, 가장 가까운 것부터 선택하며 relax하고 최적 값일 경우 shortest path에 추가하게 된다.

앞서 언급한 것 처럼, 어떤 두 노드 사이 최소 경로는 항상 그것을 포함하는 더 긴 경로의 subset이므로 각 stage에서 두 노드 사이 최소 경로를 선정하면, 그 다음 단계는 해당 노드에서 또 다른 노드로 최소 경로를 찾는 것이다. (트리를 가지치듯이 계속 진행하고, 만약 경로가 겹치면 더 짧은 것 선택)

time complexity : priority queue의 time complexity를 따라감. 만약 배열을 사용한다면 O(v)*O(v)가 되고, binary heap을 사용하면 O(vlog v+Elog v)가 된다. (extract min, min-heapify, build min heap)
extract min은 get min, min-heapify를 호출해야 하므로 O(log v)가 되는 것이 자명하다. relax의 경우 heap을 구성하는 어떤 노드의 key 값이 줄어드는 것이 된다. (왜냐하면 더 짧은 shortest path를 찾을 수 있으므로) 따라서 이 역시 해당 노드의 min heapify를 해야하므로 O(log v)가 걸린다.

그러나 graph의 density가 높을 경우, Edge의 수가 node의 수의 제곱에 가까워지므로 array를 사용하는 것이 더 효율적이다. 따라서 그래프의 형상을 보고 결정해야 한다.


Bellman-ford's algorithm
위와 달리 경로가 음수여도 적용할 수 있다. 이는 각 노드마다 relaxation을 적용하여 최소 경로를 찾고, 만약 음수 경로가 존재한다면 해당 경우를 비교 확인하는 방식으로 진행된다.

time complexity : init에 O(v), 음수 경로 확인에 O(e)가 걸리고 각노드마다 진행하는 전체 relaxation에는 O(ve)가 걸린다.