다익스트라 알고리즘 (Dijkstra's Algorithm)

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

다익스트라 알고리즘(Dijkstra's Algorithm)은 네덜란드의 컴퓨터 과학자 에츠허르 다익스트라(Edsger Dijkstra)가 고안한 알고리즘으로, 그래프에서 한 노드(정점)에서 다른 모든 노드까지의 최단 경로를 찾는 알고리즘이다. 이 알고리즘은 가중치가 있는 그래프에서 사용되며, 특히 가중치가 음수가 아닌 경우에 유효하다.

동작 원리

1. 시작 노드 설정
시작 노드를 설정하고, 시작 노드에서 다른 모든 노드로의 거리를 무한대로 설정한다. 시작 노드의 거리는 0으로 설정한다.

2. 미방문 노드 집합 설정
모든 노드를 미방문 노드 집합에 넣는다.

3. 최단 거리 노드 선택
처음에는 시작노드가 선택되고, 이후에는 미방문 노드 중에서 현재 가장 짧은 거리를 가진 노드를 선택한다.

4. 거리 업데이트
현재 노드와 연결된 인접 노드의 거리를 계산하고, 그 거리가 기존에 기록된 거리보다 짧으면 업데이트한다.
즉, 인접 노드까지의 거리 = 현재 노드까지의 거리 + 현재 노드에서 인접 노드로 가는 거리.

5. 노드 방문 완료 처리
현재 노드를 방문 완료 처리하고, 미방문 노드 집합에서 제거한다.

6. 반복
모든 노드가 방문 완료 처리될 때까지 3~5 과정을 반복한다.

예시

[백준 1916번: 최소비용 구하기]

위 이미지와 같이 정점과 간선으로 이루어져 있다고 가정하자.
이렇게 가중치가 주어진 그래프에서 어떤 출발노드로부터 모든 노드의 최소 비용을 알고싶다면, 다익스트라 알고리즘으로 문제를 해결할 수 있다.
노드 1에서부터 시작하여 모든 노드들의 최소비용을 구하고 싶다고 가정하자.
먼저, 시작 노드를 제외한 모든 노드들의 비용을 무한으로 설정하고, 모든 노드들을 미방문 노드로 설정한다.
시작 노드의 비용은 0으로 설정한다
 
- 방문 체크 배열 visited

0

false

false

false

false

 

- 노드들의 비용 cost

1	2	3	4	5
INF	INF	INF	INF	INF

 
이제 시작노드인 1을 방문해보자.

visited 배열에 노드1에 대한 방문 처리를 해준다.
- 방문 체크 배열 visited

true

false

false

false

false

노드 1과 인접한 노드들의 가중치를 계산하여 cost 배열을 업데이트 해준다.
현재 방문한 노드1의 비용은 0이다. 각 인접 노드 가중치에 + 0 을 해준 값을 업데이트해주면 된다.

- 노드들의 비용 cost

0

2

3

1

10

 
방문하지 않은 노드 중, 가장 작은 비용을 가진 노드는 노드4이다. 이 노드를 다음 방문 노드로 설정하여 탐색을 진행한다.

방문한 노드에 대하여 visited 배열에 체크해주고,
방문하지 않은 인접노드에 대하여, 현재 방문 노드의 비용 + 인접 노드의 가중치를 계산한다.
이 값이 cost에 저장된 값보다 작다면 cost를 변경해준다.
 
- 방문 체크 배열 visited

true

false

false

true

false

- 노드들의 비용 cost

0

2

3

1

4

다음 탐색 노드는, 방문하지 않은 노드 중 가장 작은 비용을 가진 노드2이다.
이후 진행은 설명없이 그래프와 cost, visited 표로 설명하겠다.

- 방문 체크 배열 visited

true

true

false

true

false

- 노드들의 비용 cost

0

2

3

1

4

- 방문 체크 배열 visited

true

true

true

true

false

- 노드들의 비용 cost

0

2

3

1

4

 
이제 마지막 노드5를 방문하고 나면 더 이상 미 방문 노드가 없으므로 탐색을 종료한다.
그럼 최종적으로 노드1에서 출발하는 모든 노드의 최소 비용은 다음과 같다.

0

2

3

1

4

 
이를 Java로 구현한 것은 아래의 링크에서 확인할 수 있다
[백준/Gold V] 최소비용 구하기 - 1916

[백준/Gold V] 최소비용 구하기 - 1916

 
 
 
 
 

다익스트라 알고리즘의 한계

가중치가 있고, 모든 정점의 최소 비용을 알고싶을 때 다익스트라를 사용하지만 아래와 같은 한계점이 있다.

• 시간 복잡도
  다익스트라 알고리즘의 시간 복잡도는 힙(heap)을 사용하는 경우 `O((V+E) log⁡V)`이다.
  여기서 V는 노드의 수, E는 엣지의 수이다.
  때문에, 노드와 엣지가 많은 큰 그래프에서는 효율적이지 않다.
  
  
• 전 영역 탐색
  다익스트라 알고리즘은 시작 노드에서 모든 노드까지의 최단 경로를 찾기 때문에 목표 노드만 필요할 경우에도 불필요한 계산이 많이 발생한다.
  
  
• 음수 가중치 문제
  다익스트라 알고리즘은 음수 가중치를 다루지 못한다. 이 경우에는 벨만-포드 알고리즘을 사용하는것이 좋다.
  
  

 
 

사용 사례

• 네트워크 라우팅: 인터넷 라우팅 프로토콜에서 최단 경로를 찾기 위해 사용
• 지도 서비스: Google Maps와 같은 지도 서비스에서 두 지점 간의 최단 경로를 찾기 위해 사용
• 교통 시스템: 교통 네트워크에서 최단 경로를 찾아 효율적인 경로를 제공하는 데 사용
• 로봇 경로 계획: 로봇이 장애물을 피해 목적지까지 이동하는 최단 경로를 찾는 데 사용