# Shortest Path Algorithm

Minimum Spanning Tree란
---
- 그 전에 Spanning Tree 란: 그래프의 최소 연결 부분 그래프. 최소 연결이라함은 간선의 수가 가장 작은 것. 즉, 최소한의 간선으로 모든 노드를 연결할 수 있을 때, 생기는 그래프들
- Minimum spanning tree 는 spanning tree 중 간선의 가중치의 합이 최소인 tree를 의미함. 특징으로는 cycle 이 포함되어서는 안되고, 반드시 n-1 개의 간선만 사용해야한다.
- MST 를 구현하는 방법 1) Kruskal MST 알고리즘: greedy method를 이용하여 네트워크의 모든 정점을 최소 비용으로 연결하는 최적의 해답을 구하는 것. 방법은 간선을 오름차순으로 정렬하고, 정렬된 간선 리스트에서 사이클을 형성하지 않는 간선을 선택하는데, 이 때 가중치가 가장 낮은 간선부터 선택한다
- MST 를 구현하는 방법 2) Prim MST 알고리즘. 간선 선택하는 Kruskal 과 다르게 정점 (vertex) 선택 알고리즘임. 초기값으로는 시작점이 집합에 포함. 앞단계에서 만들어진 MST 집합의 정점들 중 최소 간선으로 연결된 정점을 선택하여 집합에 포함 (즉, 가장 가중치가 낮은 정점을 멈ㄴ저 선택) 집합이 N-1 개가 될때까지 반복

#### Prim's Algorithm
- Dijkstra 알고리즘과 상당히 비슷하다
- :face_with_monocle:

#### Kruskal's Algorithm
- :face_with_monocle:

Dijkstra Algorithm
---
- 한 노드에서 다른 (모든) 노드까지의 최단 거리를 계산하는 알고리즘으로, 음이 아닌 가중치를 갖는 간선을 갖고 있는 그래프에서 사용된다. 지금까지 구한 값에 바로 다음 값을 비교해서 업데이트를 하는 방식으로 greedy algorithm 이라고 볼 수 있다.
- (비교: Bellman Ford 알고리즘 - 음의 가중치를 갖는 그래프, Floyd Warshall 알고리즘 - 모든 노드에서 모든 노드로 가는 최단 거리를 계산하는 알고리즘, BFS 알고리즘 - 가중치가 없는 그래프)
- 특징
- 그리디 알고리즘
- 우선순위큐
- 음의 가중치 적용 x
- 단점으로는 음의 가중치 적용 안됨과 블라인드 서치라는 점
- 왜 음의 가중치는 처리할 수 없을까?
- :face_with_monocle:

Bellman-Ford Algorithm
---
- Dijkstra ALgorithm 이 음의 가중치를 처리하지 못하는 이유 때문에 Dijkstra 와 아주 유사하지만 BFS를 접목한 Bellman-Ford Algorithm 이 사용됨.
- 시간 복잡도는 O(V*E)로 Dijkstra 보다는 시간이 좀더 걸린다.

Floyd Warshall Algorithm
---
- 왜 쓰냐? 모든 vertex 의 pair 의 shortest path problem 을 해결하기 위함
- 특징
- 3중 for문을 사용함
- 인접행렬을 사용함