다익스트라(Dijkstra) 알고리즘이란?

**하나의 출발점에서 다른 모든 정점까지의 최단 경로를 찾는 알고리즘**이다. 다익스트라 알고리즘은 플로이드 워샬 알고리즘과 달리 음수 가중치를 가진 그래프에는 적용할 수 없으며, 그래프의 간선 가중치는 양수여야 한다. 아직까지 음의 가중치를 가진 그래프 문제를 풀어본적 없어 플로이드 워샬과 어떤식으로 나뉘는지 확 와 닿지는 않는 듯 하다.

다익스트라 알고리즘의 주요 원리는 **"출발점으로부터 현재까지 발견된 최단 거리가 가장 짧은 정점"을 선택하고, 해당 정점과 인접한 정점들을 탐색하여 최단 거리를 갱신하는 것**이다. 이 과정을 모든 정점을 탐색할 때까지 반복한다.

다음은 다익스트라 알고리즘의 동작 과정이다

1. 초기화: 출발점에서 각 정점까지의 거리 값을 무한대로 설정하고, 출발점 자체의 거리 값을 0으로 설정한다.
2. 방문하지 않은 정점 중 최단 거리가 가장 짧은 정점 선택: 방문하지 않은 정점 중에서 현재까지 발견된 최단 거리가 가장 짧은 정점을 선택한다.
3. 선택한 정점과 인접한 정점들의 최단 거리 갱신: 선택한 정점과 인접한 모든 정점들에 대해, 현재까지 발견된 최단 거리와 해당 간선의 가중치를 비교하여 더 짧은 경로가 있다면 해당 값을 업데이트한다.
4. 반복: 모든 정점을 방문할 때까지 2번과 3번 단계를 반복한다.

다익스트라 알고리즘은 욕심쟁이(Greedy) 기법을 사용하여 작동한다. **시간 복잡도는 O(V^2) 또는 O(E log V) (V는 그래프 내의 노드 수, E는 엣지의 수)**인데, 이 중 후자인 힙(heap) 자료구조를 사용하는 경우 보다 일반적으로 후자가 선호된다.

주로 네트워크 라우팅, GPS 네비게이션 시스템 등에 사용된다고 한다.