다익스트라

🤔 다익스트라 란?

• 그래프에서 특정 노드에서 다른 노드들의 최단 거리를 구하는 알고리즘이다.
• 이때, 에지는 모두 양수의 값을 가져야하고, 시간 복잡도는 O(에지수log(노드수)) 이다.

👉 다익스트라 수행 방식

다익스트라 수행 방식 1

다익스트라 수행 방식 2

▣ 오류!!!

위 그림에서는 인접한 노드를 큐에 넣어 순서대로 수행했는데, 다익스트라 알고리즘에서는 가중치가 작은 값을 기준으로 큐에 넣어주어야 한다.따라서, 우선 순위 큐를 활용하여 에지 가중치를 기준으로 정렬되어 수행해주어야 한다.
수행 방식은 동일하지만, 에지 가중치를 기준으로 다익스트라 알고리즘이 수행되어야 할 것!!!! (인접한 노드 기준 xxxxx)

✔️ 다익스트라 수행 과정

1. 그래프를 인접 리스트로 구현한다.
2. 방문 리스트와 최단 거리 리스트를 초기화한다.
   이때, 최단 거리 리스트에서는 출발 노드는 0, 나머지 노드에는 무한히 큰 값을 넣어주면 된다.
3. 최단 거리 리스트에서 가장 작은 가중치부터  시작하여, 인접 리스트에 저장되어 있는 에지 가중치 값을 최단 거리 리스트에서 업데이트 시켜준다.
   최단 거리 업데이트 방법은 자신의 최단 거리 리스트 값 + 인접 노드로 가는 에지 가중치와 인접한 노드의 최단 거리 리스트 값을 비교하여 최솟값으로 업데이트를 시켜준다.
4. 한번 방문한 노드는 방문 리스트를 업데이트 시켜준다.
5. 3, 4번 수행 과정을 반복한 후, 모든 노드를 탐색하여 최단 거리 리스트를 완성할 수 있다.