최소 경로 | Shortest Path

그래프의 최소경로를 구하는 알고리즘이다.
크게 다익스트라 알고리즘과 플로이드 워셜 알고리즘이 있다.

기본적으로 [그래프](../DATA STRUCTURE/Graph.md) 자료구조 이해를 바탕으로 사용 가능하다

✒ 블로그 글 작성 함

다익스트라(데이젝스트라) 알고리즘 | Dijkstra Algorithm

V가 정점(노드)의 개수이고 E가 간선의 개수일 때 다음과 같은 시간 복잡도를 갖는다.

시간 복잡도를 통해 알 수 있듯이 우선 순위 큐(Priority Queue)를 사용하여 구현하는 것이 효율성이 높다.

그래프의 인접 리스트를 이용하여 문제를 해결한다.
때문에 플로이드 워셜 알고리즘보다 공간 복잡도면에서 우수하다

V가 정점(노드)의 개수일 때 O(V³) 시간 복잡도를 갖는다.
다익스트라 알고리즘에서 인접 리스트를 사용하는 것과 달리 인접 행렬를 사용한다.

플로이드 워셜 알고리즘을 사용하기 위해서 다음 점화식만 기억하면 된다.
D_ab = min(D_ab , D_ak + D_kb)