최단경로

말 그대로 가장 짧은 경로를 찾는 알고리즘 이다.

---

1. 다익스트라

📢특정한 노드에서 출발하여 다른 특정 지점까지의 각각의 최단 경로를 구해주는 알고리즘.

1. 그리디 알고리즘이다.
2. 방문하지 않은 노드 중에서 현재 최단 거리가 가장 짧은 노드를 계속 수정해준다.
3. 시간 복잡도: O(ElogV) {V : 노드 개수, E: 간선 개수}

✨다익스트라 정리

2. 플로이드 워셜

📢모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 상황

1. DP 알고리즘이다.
2. 시간 복잡도:
   O(N³)

✨플로이드 워셜 정리

3. 벨만 포드

📢음의 간선이 주어졌을 경우 사용. 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘. + 사이클을 파악하고 싶을 때

✨벨만 포드 정리

---

• ✨다익스트라 : 단계마다 최단거리를 가지는 노드를 하나씩 반복적으로 선택
• ✨플로이드 워셜: 단계마다 거쳐 가는 노드를 기준으로 알고리즘 수행