[알고리즘] SSP(2) 다익스트라(Dijkstra)란?

다익스트라란

• 하나의 시작 정점으로부터 모든 다른 정점까지의 최단 경로를 찾는다.
• 프림알고리즘은 MST를 만들기 위해 가중치와 정점의 KEY값을 비교하여 KEY값의 업데이트 여부를 결정했다. SSP에서는 이를 Relax라고 표현했다. Relax는 key값이 없고 최단 경로 추정 값(d[v]를 이용하여 d[v]를 업데이트 할지 말지를 결정했다. Relax는 정점의 KEY값이 딱 주어진 것이 아니라 최단 경로 추정 값들이 누적되어온 결과이다. 이런 점에서 프림 알고리즘과 다익스트라 알고리즘은 다른 것을 볼 수 있다.
• 결과적으로 다익스트라는 프림 알고리즘과 비슷하기 때문에 [자료구조] MST(2) 프림(Prim) 참고

[자료구조] MST(2) 프림(Prim)이란?

---

 

다익스트라 알고리즘 동작과정

다익스트라 알고리즘은 우선 모든 정점들을 최소 우선순위 큐에 삽입한다. 그리고 최단경로 가중치 값 d[v]이 가장 작은 정점을 선택하여 인접 간선들에 대해 Relax를 수행하여 시작 정점으로부터 각 정점까지의 최단 경로 비용을 계산한다.

초기화된 그래프 모습이다.

시작 정점을 제외하고 모든 정점의 d[v]값은 ∞이다.

 

최소 우선순위큐에서 d[v]값이 가장 작은 정점을 추출하므로 v1 정점을 시작으로 하여 간선을 확장해 나간다.

---

인접한 간선을 선택하여 Relax를 수행한다.

가중치가 8인 간선을 선택할 수도 있으며, 선택 순서는 구현하기 나름이다.

 

Step 1에서 

으로 업데이트 된다.

---

Step 2와 같이 Relax를 수행하여 d[v4]=8 로 업데이트 한다.

---

v1의 인접 간선들에 대해 모두 Relax를 수행했으므로,

다음 정점을 선택하기 위해 d[v]가 가장 작은 정점을 추출한다.

따라서 정점 v2가 추출이 되어 인접 간선들에 대해 Relax를 수행하게 된다.

---

---

Relax 결과  d[v4]를 업데이트 하지 않는다.

즉 ( v1 , v4 )의 최단 경로는 v1 -> v4 이다.

---

---

v2의 모든 인접간선에 대해 Relax를 수행했으므로

최소 우선순위 큐에서 d[v]값이 가장 작은 정점을 추출하여 정점 v5가 추출된다.

---

---

---

v5의 모든 인접간선에 대해 Relax를 수행했으므로

최소 우선순위 큐에서 d[v]값이 가장 작은 정점을 추출하여 정점 v4가 추출된다.

---

---

값이 같을 경우에는 업데이트는 해도되고 안해도 된다.

하지만 그냥 가만히 두는 편이 연산을 줄인다.

---

v4의 모든 인접간선에 대해 Relax를 수행했으므로

마지막 정점 v3가 추출된다.

---

---

 

Dijkstra's 알고리즘은 Prim's 알고리즘과 유사한 방식이지만 key 값을 사용하는 것이 아닌 최단 경로 추정 값 d[v]을 사용하며 업데이트를 할 때도 그대로 가중치를 업데이트 하는 것이 아니라 이전 정점까지의 최단 경로 추정 값 d[v] + 가중치 값을 업데이트한다.

 

SSP는 최단 경로와 그 비용을 구하는 것이 목적이기 때문이다.

 

결과 트리를 보면 각 정점의 d[v] 값은 시작 정점으로부터 그 정점까지의 최단 경로 비용을 의미한다.

예를들어, d[v5]의 값은 7이므로 v1 -> v5 까지의 최단 경로 비용은 7이다.

실제로 v1 -> v2 -> v5의 경로 상 모든 가중치를 더하면 7임을 확인할 수 있다.

 

여기서 "최단 경로" 자체를 구하고 싶을 수가 있다.

그래서 Relax의 결과로 d[v] 값이 업데이트가 되면 추출된 정점을 부모노드로 설정해줌으로써 각 정점의 부모 정점을 기억할 수 있다. 예를들어, Step 2에서 Relax 결과 업데이트가 되었으므로 정점 v2의 부모는 v1이 되는 것이다.

 

Dijkstra's 알고리즘은 최소 우선순위 큐를 사용하여 d[v]값이 작은 정점을 하나씩 뽑아 인접 간선들에 대해 Relax를 수행하여 SSP를 구현한다. 동작 방식은 Prim's 알고리즘과 유사하지만 완전히 같지는 않다.

---

 

다익스트라 알고리즘 효율

네트워크에 n개의 정점이 있다면, Dijkstra의 최단경로 알고리즘은 주반복문을 n번 반복하고 내부 반복문을 2n번 반복하므로 O(n2)의 복잡도를가진다.