[알고리즘] 다익스트라 알고리즘 (Dijkstra’s algorithm)

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

다익스트라(Dijkstra) 알고리즘은 다이나믹 프로그래밍(Dynamic Programming)을 활용한 최단 경로 탐색 알고리즘이다.

 

해당 알고리즘은 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 구할 때 사용한다.

---

🔎 다익스트라(Dijkstra) 알고리즘은 왜 다이나믹 프로그래밍(Dynamic Programming) 문제인가?

다익스트라(Dijkstra) 알고리즘은 최단 경로 탐색은 '최단 거리는 여러 개의 최단 거리로 이루어져 있다.' 라는 접근 방식을 사용한다.

 

작은 문제가 큰 문제의 부분 집합에 속해있다 볼 수 있으므로 다이나믹 프로그래밍(Dynamic Programming) 문제로 분류된다.

 

다익스트라(Dijkstra) 알고리즘은 하나의 최단 거리를 구할 때 그 이전까지 구하였던 최단 거리의 정보를 그대로 사용한다.

---

💡 다익스트라(Dijkstra) 알고리즘

📌 다익스트라(Dijkstra) 알고리즘은 음수의 가중치를 가지는 간선을 포함하는 경우 사용할 수 없다.

 

아래 주어진 자료의 정점과 간선정보를 가진 그래프가 존재하는 경우, 1번 정점에서 다른 모든 정점으로 가는 최단 경로를 구해보자.

1. 그래프의 정보를 담은 인접 리스트 또는 인접 배열을 생성한다.

 

2. 정점 방문 여부를 확인하기 위한 일차원 방문 배열과 최단 거리를 저장할 일차원 거리 배열을 생성해준다.

// 방문 배열 (정점의 개수 N)
boolean[] visited = new boolean[N];

// 거리 배열
int[] dist = new int[N];

 

3. 시작 정점의 방문 체크와 거리 배열의 초기값을 INF값(MAX_VALUE)로 설정해준다.

visited[1] = true;

Arrats.fill(dist, Integer.MAX_VALUE);

 

4. 거리의 최솟값을 구하여 거리 배열을 업데이트 해준다.

• 시작 정점과 인접한 정점 중, 방문하지 않은 정점들을을 탐색한다.
• 해당하는 정점들에 대해 아래 작업을 반복한다.
• 탐색 정점의 거리 배열 거리 값과 [시작 정점의 거리 값 + 탐색 정점 거리 값]을 비교한다.
• 더 작은 값으로 거리 배열 값을 업데이트 해준다.

// 1번 정점과 인접한 정점 중 방문하지 않은 정점 - 2, 4, 5
for(int i = 0; i < adjList[1].size(); i++) {
    if (!visited[adjList[1].get(i)] && dist[2] > dist[1] + dist[2]) {
        dist[2] = dist[1] + dist[2];
    }
}

 

5. 업데이트된 거리 배열의 방문하지 않은 정점 중, 최소값을 가진 정점에 대해 위의 단계를 반복한다.

   

6. 모든 정점에 대해 단계를 반복한 후, 거리 배열의 결과가 시작 정점에서 다른 모든 정점까지의 최단 경로 탐색 결과이다.

---

⏳ 시간복잡도(Big-O)

• 인접 행렬로 구현 시, 시간 복잡도는 O(N^2)이다. 
  • 간선이 많은 그래프의 경우, 인접 행렬을 통해 빠르게 연결 여부를 확인할 수 있으므로 인접 행렬이 유리하다.
• 인접 리스트로 구현 시, 시간 복잡도는 O(N*logN)이다.
  
  • 간선이 적은 그래프의 경우, 인접 리스트를 통해 인접 노드를 빠르게 확인할 수 있으므로 인접 리스트가 유리하다.

선형 탐색으로 시간 초과가 나는 경우, 인접 리스트로 접근해야 한다. (우선순위 큐, Priority Queue)