[Algorithm] Djikstra

Djikstra (다익스트라)

• 다익스트라 알고리즘은 그래프에서 최단 거리를 구하는 알고리즘으로 다음과 같은 특징을 가지고 있습니다.

기능	특징	시간 복잡도
출발 노드와 모든 노드 간의 최단 거리 탐색	가중치는 모두 양수	O(ElogV)

다익스트라 알고리즘 단계

1. 인접리스트로 그래프 구현

• 인접 행렬로 구현하는 것보다 시간 복잡도 측면에서 N이 클 것을 대비해 인접 리스트로 구현하는 것이 좋습니다

2. 최단 거리 배열 초기화

• 최단 거리 배열을 만들고 출발 노드는 0, 이외의 노드는 무한(INF)로 초기화 합니다. 보통 INT_MAX를 사용합니다

3. 가중치가 가장 작은 노드 선택

• 최단 거리 배열에서 값이 가장 작은 노드를 고릅니다. 위에서는 값이 0인 출발 노드에서 시작합니다

4. 최단 거리 배열 업데이트

• 선택된 노드에 연결된 가중치 값을 바탕으로 다른 노드의 최단 거리를 업데이트 합니다.
• $Min(Dist[next], Dist[now] + weight[next])$

5. 3~4 단계를 모든 노드가 선택될 때까지 반복