다익스트라 알고리즘에 대해 설명해보세요

---

다익스트라 알고리즘의 정의

• 다익스트라 알고리즘은 그래프 안의 한 노드에서 다른 노드까지의 최단 경로를 구하는 알고리즘이다.

• 매 번 최단 경로의 노드를 선택하여 탐색하므로 도착 노드 뿐 아니라 다른 노드까지 최단 경로로 이동한다.

• 음수의 가중치 간선은 없다고 가정한다.

---

다익스트라 알고리즘의 작동 방식

1. 시작 노드를 선택한다.

2. 시작 노드를 기준으로 각 노드의 최소 비용을 저장한다.

3. 방문하지 않은 노드 중에서 최소 비용으로 연결된 노드를 선택한다.

4. 선택한 노드를 거쳐서 특정 노드로 가는 경우를 고려하여 최소 비용을 업데이트한다.

5. 목표 노드에 도달할 때까지 3, 4번을 반복한다.

---

다익스트라 알고리즘의 구현

• 노드를 탐색하는 과정에서 두 가지 구현 방법이 있다.

1. 순차 탐색
   : 순차 탐색의 경우 N*N 개의 인접 행렬을 만들어서 노드의 개수만큼 순차적으로 탐색하는 방법이다. O(N^2)의 시간 복잡도를 가진다.

2. 우선순위 큐
   : 우선순위 큐는 최소 힙으로 구현하여 순차 탐색과는 다르게 방문 여부를 기록할 배열이 필요가 없다. O(N logN)의 시간 복잡도를 가진다.

---

결론

다익스트라 알고리즘은 시작 노드로부터 목표 노드까지 최단 경로를 찾는 알고리즘입니다. 하나의 최단 거리를 구할 때 그 이전까지 구했던 최단 거리를 그대로 사용하기 때문에 DP(Dynamic Programming) 문제이기도 합니다. 노드를 연결하면서 최소 비용 테이블을 업데이트하며 목표 노드에 도달하게 됩니다. 구현 방법에는 인접 행렬을 이용한 순차 탐색과 최소 힙을 이용한 우선순위 큐, 두 가지 방법이 있습니다.