[Java] 다익스트라(Dijkstra) 알고리즘

다익스트라 알고리즘이란?

BFS와 DP를 활용한 최단경로 탐색 알고리즘이다. 즉, 그래프에서 출발점에서 목표점까지의 최단거리를 구할 때 사용하는 알고리즘이다. 이 과정에서 도착 정점 뿐만 아니라 모든 다른 정점까지 최단 경로로 방문하며 각 정점까지의 최단 경로를 모두 찾게 된다. 매번 최단 경로의 정점을 선택해 탐색을 반복하는 것이다.

 

❓왜 다이나믹 프로그래밍일까?

하나의 최단 거리를 구할 때 그 이전까지 구했던 최단 거리 정보를 그대로 사용하기 때문이다.

 

다익스트라 알고리즘 특징

1. 그래프 내부 하나의 정점(노드, Vertex)에서 다른 모든 정점으로 가는 최단 경로를 알려줌
2. 그래프의 간선(Edge)마다 가중치가 존재할 때 사용
   ⇒ BFS를 활용한 최단 경로 구하기와 다른 점
3. 간선의 음의 가중치는 존재하지 ❌. 음의 가중치가 하나라도 있으면 다익스트라를 사용할 수 ❌
   ⇒ 현실 세계에 사용하기 적합한 알고리즘 [ex) GPS, 내비게이션]
4. 구현
   1. 출발 노드, 도착 노드로 구성된 이차원 배열 활용 구현
   2. 각 거리에 해당하는 우선순위 큐(힙) 활용 구현

 

동작 단계

1. '최단 거리 테이블'을 초기화
2. 현재 위치한 노드의 인접 노드 중 방문하지 않은 노드를 구별하고, 방문하지 않은 노드 중 거리가 가장 짧은 노드를 선택 → 방문 처리
3. 해당 노드를 거쳐 다른 노드로 넘어가는 간선 비용(가중치)을 계산해 '최단 거리 테이블'을 업데이트
4. 3 ~ 4의 과정을 반복

'최단 거리 테이블'은 1차원 배열로, N개 노드까지 오는 데 필요한 최단 거리를 기록. N개(1부터 시작하는 노드 번호와 일치시키려면 N + 1개) 크기의 배열을 선언하고 큰 값을 넣어 초기화시킨다.

'노드 방문 여부 체크 배열'은 방문한 노드인지 아닌지 기록하기 위한 배열로, 크기는 '최단 거리 테이블'과 같다. 기본적으로는 False로 초기화하여 방문하지 않았음을 명시한다.

 

동작 예

1. 아직 방문하지 않은 정점들 중 거리가 가장 짧은 정점을 하나 선택해 방문한다.
2. 해당 정점에서 인접하고 아직 방문하지 않은 정점들의 거리를 갱신한다.

1. 시작 노드를 0이라고 설정을 하고, 이웃한 노드 중 거리가 가장 짧은 순으로 노드를 선택해 가중치(7, 9, 14)를 각각 1, 2, 5번 노드에 기록한다.
2. 1번에서 탐색한 노드(1)의 이웃한 노드 중 거리가 짧은 순으로 노드를 탐색한다.
   • 처음 탐색하는 노드 : 기록된 가중치 + 간선 가중치
   • 재 탐색하는 노드 : 기록된 가중치 + 간선 가중치와 기록되어 있는 가중치 중 작은 것 기록
     ⇒ 이유 : 직접 이웃한 정점으로 가는 것보다 이웃한 다른 정점을 거쳐서 가는 것이 더 적은 비용이 들 수도 있기 때문
   • 예) 1번 노드에 인접한 3번 노드 : 7 + 15 = 22 기록.
     1번 노드에 인접한 2번 노드 : 9로 기록되어 있으므로 7 + 10 = 17과 9 중 작은 9를 기록

 

구현 1. 이차원 배열 활용 구현

가중치를 가중치 인접 행렬인 2차원 배열에 저장해보자. 연결되어있지 않은 노드끼리는 무한대 가중치로 저장한다.

가중치 인접 행렬

	0	1	2	3	4	5
0	0	7	9	∞	∞	14
1	7	0	10	15	∞	∞
2	9	10	0	11	∞	2
3	∞	15	11	0	6	∞
4	∞	∞	∞	6	0	9
5	14	∞	2	∞	9	0

시작 노드를 0으로 초기화 하며 각 노드까지의 최소 가중치를 기록할 배열을 선언한다.

나머지 노드의 가중치는 무한대로 초기화 한다.

 

가중치 기록 배열 (0번 노드)

0	1	2	3	4	5
0	∞	∞	∞	∞	∞

 

 

0번 노드

가중치 기록 배열

0	1	2	3	4	5
0	7	9	∞	∞	14

 

각 노드의 가중치 기록 배열을 dist, 가중치 인접 행렬 2차원 배열을 d라 하자.

1. 시작 노드(0번)를 통해 n번 노드로 가는 거리 : dist[0] + d[0][n]
2. 만약, dist[0] + d[0][n] < dist[n] : dist[n]이 갱신.

 

지금은 0번 노드를 제외한 모든 노드로의 dist 값이 무한대이므로 모두 갱신된다.

그다음 인접 노드(1, 2, 5번)의 인접 노드를 탐색하며 값을 수정해나간다.

 

1번 노드

가중치 기록 배열

0	1	2	3	4	5
0	7	9	∞ → 22	∞	14

 

dist[1] + d[1][3] == 7 + 15 == 22 , dist[3] == ∞ 이므로 dist[3] = 22가 된다.

시작 노드(0번)에서 1번 노드까지의 가중치는 7이다.

1. 1 → 2번 노드의 간선 가중치는 10이므로, 기록된 가중치(0 → 1) + 간선 가중치(1 → 2) = 7 + 10 = 17가 된다.
   ⇒ 이 값은 0 → 2번 노드에 기록된 가중치 9보다 크므로 변경하지 않고 넘어간다.
2. 1 → 3번 노드의 간선 가중치는 15이므로, 기록된 가중치(0 → 1) + 간선 가중치(1 → 3) = 7 + 15 = 22가 된다.

 

2번 노드

가중치 기록 배열

0	1	2	3	4	5
0	7	9	22 → 20	∞	14 → 11

 

dist[2] + d[2][3] == 9 + 11 == 20 , dist[3] == 22 이므로 dist[3] = 20가 된다.

시작 노드(0번)에서 2번 노드까지의 가중치는 9이다.

1. 2 → 3번 노드의 간선 가중치는 11이므로, 기록된 가중치(0 → 2) + 간선 가중치(2 → 5) = 9 + 11 = 20이 된다.
   ⇒ 이 값은 0 → 3번 노드에 기록된 가중치 22보다 작으므로 20으로 변경한다.
2. 2 → 5번 노드의 간선 가중치는 2이므로, 기록된 가중치(0 → 2) + 간선 가중치(2 → 5) = 9 + 2 = 11이 된다.
   ⇒ 이 값은 0 → 5번 노드에 기록된 가중치 14보다 작으므로 11로 변경한다.

 

5번 노드

가중치 기록 배열

0	1	2	3	4	5
0	7	9	20	∞ → 20	11

 

dist[5] + d[5][4] == 11 + 9 == 20 , dist[4] == ∞ 이므로 dist[4] = 20가 된다.

시작 노드(0번)에서 5번 노드까지의 가중치는 11이다.

1. 5 → 4번 노드의 간선 가중치는 9이므로, 기록된 가중치(0 → 5) + 간선 가중치(5 → 4) = 11 + 9 = 20이 된다.
   ⇒ 이 값은 0 → 4번 노드에 기록된 가중치 ∞보다 작으므로 20으로 변경한다.

 

3번 노드

가중치 기록 배열

0	1	2	3	4	5
0	7	9	20	20	11

 

dist[3] + d[3][4] == 20 + 6 == 26 , dist[4] == 20 이므로 dist[4] = 20가 된다.

1. 3 → 4번 노드의 간선 가중치는 6이므로, 기록된 가중치(0 → 3) + 간선 가중치(3 → 4) = 20 + 6 = 26이 된다.
   ⇒ 이 값은 0 → 4번 노드에 기록된 가중치 20보다 크므로 변경하지 않는다.

 

마지막 4번 노드는 이웃한 모든 노드가 탐색을 완료한 상태기 때문에 더이상 탐색하지 않는다.

 

최종 결과 테이블

0	1	2	3	4	5
0	7	9	20	20	11

• 시작 노드(0번 노드)부터 1번 노드까지 최단 거리 : 7
• 시작 노드(0번 노드)부터 2번 노드까지 최단 거리 : 9
• 시작 노드(0번 노드)부터 3번 노드까지 최단 거리 : 20
• 시작 노드(0번 노드)부터 4번 노드까지 최단 거리 : 20
• 시작 노드(0번 노드)부터 5번 노드까지 최단 거리 : 11

 

이차원 배열 활용 구현의 시간 복잡도

'방문하지 않은 노드 중 거리값이 가장 작은 노드'를 선택해 다음 탐색 노드로 삼는다. 그 노드를 찾는 방식이 순차 탐색이 된다. 즉, 거리 테이블의 앞에서부터 찾아내야 하므로 노드의 개수만큼 순차 탐색을 수행해야 한다. 따라서 노드 개수가 N이라고 할 때 각 노드마다 최소 거리값을 갖는 노드를 선택해야 하는 순차 탐색이 수행되므로 (N−1)×N=O(N^2)의 시간이 걸린다.

 

dist 값이 제일 작은 노드를 찾는 부분을 우선순위 큐를 이용하면 O(log V)로 줄일 수 있다.

우선순위 큐 활용 구현을 보자.

 

구현 2. 우선순위 큐 활용 구현

우선순위 큐에서 사용할 '우선순위'의 기준은 '시작 노드로부터 가장 가까운 노드'가 된다. 따라서 큐의 정렬은 최단 거리인 노드를 기준으로 최단 거리를 가지는 노드를 앞에 배치한다.

위의 순차 탐색을 쓰는 구현과는 다르게 우선순위 큐를 사용하면 방문 여부를 기록할 배열은 없어도 된다. 우선순위 큐가 알아서 최단 거리의 노드를 앞으로 정렬하므로 기존 최단 거리보다 크다면 무시하면 그만이다. 만약, 기존 최단거리보다 더 작은 값을 가지는 노드가 있다면 그 노드와 거리를 우선순위 큐에 넣는다. 우선순위 큐에 삽입되는 형태는 <거리, 노드> 꼴이다.

 

정리

1. 최소 힙을 하나 마련한다.
2. 어떤 노드 u를 방문해서 인접한 노드 v의 거리를 갱신할 때마다 최소 힙에 (dist[v], v) 쌍을 넣는다.
3. 힙의 pair는 첫 번째 인자의 대소 비교를 먼저 하므로, dist 값이 작으면 작을수록 우선순위 큐에서 먼저 나오게 된다.
4. 그 두 번째 인자인 정점 번호를 사용하면 된다.

 

주의사항

1. v를 방문하기 전에 값이 여러 번 갱신될 수도 있고 서로 다른 (dist[v], v) 값들이 우선순위 큐 안에 존재할 수 있다.
   ⇒ 제일 작은 d 값 하나만 뽑아서 쓰면 되고 우선순위 큐가 이걸 자동으로 해결해 준다.
2. 1번 사항으로 인해 뽑히지 못하고 우선순위 큐에 남아있는 v 정점에 관한 쌍의 처리 문제
   : 큐에서 나온 노드가 이미 방문한 노드라면 무시하는 코드를 구현한다.

 

시간 복잡도

간선의 수를 E(Edge), 노드의 수를 V(Vertex)라고 했을 때 O(E logV)가 된다.

우선순위 큐에서 꺼낸 노드는 연결된 노드만 탐색하므로 최악의 경우라도 총 간선 수인 E만큼만 반복한다.

 

즉, 하나의 간선에 대해서는 O(logE)이고, E는 V^2보다 항상 작기 때문에 E개의 간선을 우선순위 큐에 넣었다 빼는 최악의 경우에 대해서는 O(E logV)이다.

 

Reference

https://gomgomkim.tistory.com/17

https://techblog-history-younghunjo1.tistory.com/247

https://code-lab1.tistory.com/29

https://justkode.kr/algorithm/python-dijkstra

https://techblog-history-younghunjo1.tistory.com/248?category=1014800