[자료구조] 다익스트라

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

다익스트라 알고리즘은 가중치 그래프에서 SP(최단경로) 문제를 해결하기 위해 등장한 알고리즘이다. 최단경로 문제는 두 정점을 연결하는 여러 경로들 중에서 간선들의 가중치 합이 최소가 되는 경로를 찾는 문제로, 다익스트라 알고리즘은 SP문제중 Single Source SP(시작정점 v에서 다른 모든 정점까지의 최단 경로 찾기)를 해결하기 위한 알고리즘이다. (단, 음수 간선에 대해서는 성립하지 않는다.)

---

문제 해결을 위한 기초 생각

1. 시작 노드 정하기
2. 시작 노드에서 가장 가까운 노드를 계속 탐욕적으로 선택
3. 이미 찾은 최단경로에 그 가까운 노드를 더함

더 꼼꼼히 생각해보기

3번과 같이 생각하다보면 한 노드에 접근 할 수있는 엣지가 많을 경우에는 어떤 방식이 더 빠른지 의문이 들 수 있다.

위와 같은 그래프에서 시작노드 A에서 노드 D까지의 SP를 구한다고 생각해보자. 기초생각의 2,3번과 같이 접근하면 A에서 바로 갈 수 있는 노드 중 제일 짧은 건 B(4)이고 여기서 D로가면 4 + 5 = 9이다. 반면 A에서 바로 갈 수 있는 노드 중 제일 짧은 것은 아니지만 C(6)을 선택하면 6 + 2 = 8로 A-C-D가 A에서 D로 가는 SP된다.

이런 아이디어를 반영해서 최종적으로 생각하면 다음과 같다.

 

1. 시작 노드 정하기
2. 시작 노드에서 가장 가까운 노드를 계속 탐욕적으로 선택
3. 이미 찾은 최단경로에 그 가까운 노드를 더한 값과 타겟 노드에 접근 할 수 있는 다른 방법으로 접근한 값을 비교후 더 작은 값을 선택

알고리즘 구체화하기

위의 아이디어를 구체화해보자. 필요한 것은 시작정점 v, 집합 s, dist[u] 배열이다.

• 집합 s : v에서부터의 최단경로를 이미 찾은 정점들의 집합
• dist[u] 배열 : s에 있는 정점들만을 거쳐서 가는 v-u간의 경로의 길이

로 보면 된다.

초기값은 s={v}, dist[u]=v-u간에 간선이 있으면 weight(v,u), 그렇지 않으면 무한대(보통 9999등을 넣음)로 설정한다.

매 단계에서 s안에 있지 않은 정점들 중에서 가장 dist 값이 작은 정점(u)을 s에 추가하고 s에 포함되지 않은 남은 정점들 w까지의 기존 경로와 u를 거쳐가는 경우 중에 SP를 조사한 후 s에 있지 않은 다른 정점들의 dist값을 갱신한다. 아래 그림을 보면 이해가 쉬울 것이다.

위에 있는 그래프를 가지고 SP를 구하는 단계를 보자면 다음 그림과 같다.

노란셀: 집합 s에 들어있는 정점 / 빨간글씨: 해당단계에서 sp가 변화하는 정점

 

알고리즘 실행 과정(.GIF)

출처 : https://haningya.tistory.com/116

---

참고사항

다익스트라 알고리즘을 코드로 구현시 가장 먼저 떠올릴 수 있는 것은 일반 배열로 푸는 것인데, 이렇게 해결하면 배열이 너무 커져 런타임 에러가 발생할 수 있다. 따라서 보통 우선순위 큐를 사용하여 코드를 짜는 경우가 많다.

 

우선순위 큐를 사용하는 이유는 일반 큐에 비해 속도에 이점이 있기 때문이다. 우선순위 큐는 사용자가 지정해준 우선순위가 높은 데이터부터 나오는데, 다익스트라 알고리즘은 주로 최소거리를 구하는 문제에서 사용되므로 거리가 최소인 것을 우선순위로 지정하면 일반 큐(FIFO)를 사용할 때 보다 속도가 향상된다.

---

백준 문제 풀어보기

• 다익스트라 기본 문제 1 : 1753 최단 경로 https://www.acmicpc.net/problem/1753
• 다익스트라 기본 문제 2 : 1916 최소 비용 https://www.acmicpc.net/problem/1916
• 다익스트라 기본 문제 3 : 18352 특정 거리의 도시 찾기https://www.acmicpc.net/problem/18352
• 다익스트라 심화 문제 : 1854 k번째 최단경로 (필수 X) https://www.acmicpc.net/problem/1854