# 최단거리 알고리즘

## 다익스트라
- 한 정점에서 모든 정점까지의 최단거리를 구하는 알고리즘
- 우선순위 큐를 이용하여 가장 작은 경로를 가진 정점을 빠르게 구할 수 있음
- 음수 가중치가 있을 경우 사용 불가
- 시간복잡도
- 우선순위 큐 사용
1) 다익스트라는 모든 간선을 검사함. 따라서 O(|E|)
2) 우선순위 큐에 들어갈 수 있는 최대 점의 수는 O(|E|)임. (모든 간선이 검사될 때마다 최대로 한 번 들어갈 수 있음)
여기에 추가 또는 삭제하는 시간은 O(log|E|)이므로, 전체 시간복잡도는 O(|E|log|E|)
따라서 총 시간복잡도는 O(|E| + |E|log|E|) = O(|E|log|E|)이고,
보통 |E| <= |V|2 이므로, O(|E|log|V|)라고 볼 수도 있음

- 우선순위 큐 사용 X
1) 미방문 노드 가운데 거리가 가장 작은 노드를 선택해야 함. 최악의 경우 노드 전체를 탐색해야 하므로 O(|V|)
2) 이웃노드와 연결된 간선에 대해 최단 경로를 업데이트 해야함. 한 노드당 간선의 기대값은 |E|/|V|
3) 한 정점에서 최악의 경우 시간 복잡도는 O(|V| + |E|/|V|)
4) 이를 모든 정점에서 해야하므로 O(|V|^2 + |E|)

정점의 수가 적고 간선이 많은 경우 우선순위 큐보다 빠를수도 있음

- 동작 과정

- 음수 가중치일때 안되는 이유

위 그래프의 경우 A-B-C-D 의 경로로 갔을때 거리는 60이 나옵니다. 하지만 A-B-C-A-B-C-D의 경로로 갔을때 거리는 10이 나옵니다. 이처럼 사이클을 반복할수록 작은값이 나오기 때문에 최단거리를 구하는 다익스트라를 사용 할 수 없습니다.

음의 가중치를 가진 선분이 온다고 무조건 다익스트라를 쓸 수 없는 것은 아닙니다. -100이 아니라 -10이 오는 경우 다익스트라 알고리즘을 이용하더라도 60이라는 최단거리 값을 구할 수 있습니다.

벨만 포드 역시 사이클을 돌수록 값이 감소하는 사이클(음의 사이클)이 오는 경우 최단거리를 구할 수 없지만 음의 사이클의 존재 유무를 파악할 수 있다는 점이 다른점입니다.


위 그래프에서 다익스트라 알고리즘을 활용해서 경로를 구하면 A-C까지의 최단거리는 2가 나옵니다. 하지만 A-B-C의 경로로 가는 경우 -5가 나오기 때문에 A-B-C의 경로가 최단거리입니다.
이는 다익스트라가 Greedy 알고리즘이기 때문에 발생하는 문제점입니다.

## 벨만 포드
- 한 정점에서 모든 정점까지의 최단거리를 구하는 알고리즘
- 음의 가중치가 존재할때도 최단거리를 구할 수 있음
- 음의 사이클이 존재하는 경우 최단거리를 구할 수는 없지만 최단 경로에 도달할 수 없음을 확인할 순 있음
- 시간복잡도
- 모든 Edge들을 V-1번 보면서 각 정점의 최단 거리를 찾으므로 O(|V||E|)
- V-1번째 갱신 거리와 V번째 갱신 거리를 비교했을 때 값이 달라진다면 음의 사이클이 있다고 판단할 수 있음

- 동작 과정

## 플로이드 와샬
- 모든 점들간의 최단거리를 구하는 알고리즘
- N,M의 최단거리를 구할때 K(0 < K < V)의 정점을 지나는 방식으로 최단거리를 구함
- N,M,K 세개의 값이 변화하므로 시간복잡도는 N^3

- 동작 과정