Dijkstra

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

 

다익스트라 알고리즘은 주어진 그래프에서 출발 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘입니다. 특히, 음의 가중치가 없는 그래프에서 최단 경로를 찾는 데 사용됩니다. 이 알고리즘은 그리디 알고리즘으로 분류되며, 우선순위 큐를 이용하여 효율적으로 구현됩니다.

 

기본 아이디어
1. 출발 노드에서 시작하여, 다른 모든 노드로 가는 최소 비용을 차례대로 계산합니다.
2. 최단 거리를 찾는 방법은 우선 최단 거리가 확정된 노드를 하나씩 확정하면서, 그 노드와 연결된 다른 노드들의 거리를 갱신하는 방식입니다.
3. 우선순위 큐(Priority Queue) 를 사용하여, 현재까지 계산된 최소 비용을 기준으로 가장 작은 값을 가진 노드를 먼저 처리합니다.

 

알고리즘의 단계
1. 초기화:
   - 시작 노드의 거리는 0, 나머지 모든 노드의 거리는 무한대로 설정합니다.
   - 우선순위 큐에 시작 노드를 추가합니다.
  
2. 반복:
   - 우선순위 큐에서 현재 최단 거리가 확정된 노드를 하나 꺼냅니다.
   - 해당 노드에서 인접한 모든 노드로 가는 경로를 갱신합니다.
   - 갱신된 경로가 이전에 기록된 경로보다 더 짧다면, 그 노드를 우선순위 큐에 다시 삽입하여 계속 탐색합니다.
  
3. 종료 조건:
   - 우선순위 큐가 비게 되면 알고리즘이 종료됩니다.


다익스트라 알고리즘의 구현

import java.util.;

class Dijkstra {
    private static final int INF = Integer.MAX_VALUE; // 무한대 값

    // 다익스트라 알고리즘
    public int[] dijkstra(int n, int start, int[][] graph) {
        int[] dist = new int[n + 1]; // 시작 노드에서 각 노드까지의 최단 거리
        Arrays.fill(dist, INF); // 처음에는 모든 노드의 거리를 무한대로 설정
        dist[start] = 0; // 시작 노드의 거리는 0

        // 우선순위 큐 (비용, 노드) 형태로 저장
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
        pq.offer(new int[]{start, 0}); // 시작 노드와 비용(0)을 큐에 넣음

        while (!pq.isEmpty()) {
            int[] current = pq.poll();
            int node = current[0]; // 현재 노드
            int cost = current[1]; // 현재까지의 비용

            // 이미 방문한 노드이면 skip
            if (cost > dist[node]) continue;

            // 인접한 노드들 탐색
            for (int next = 1; next <= n; next++) {
                if (graph[node][next] != 0) { // 연결된 노드가 있으면
                    int newCost = cost + graph[node][next];
                    if (newCost < dist[next]) { // 새로운 경로가 더 짧으면
                        dist[next] = newCost;
                        pq.offer(new int[]{next, newCost}); // 우선순위 큐에 넣음
                    }
                }
            }
        }
        return dist; // 모든 노드에 대한 최단 거리가 담긴 배열 반환
    }

    public static void main(String[] args) {
        Dijkstra dijkstra = new Dijkstra();
        
        // 노드 수 (6), 출발 노드 (1)
        int n = 6;
        int start = 1;

        // 그래프 (2차원 배열로 표현, 인접 행렬)
        int[][] graph = new int[n + 1][n + 1]; // 그래프 초기화 (0으로 채워짐)
        
        // 예시 그래프의 간선 정보 추가
        graph[1][2] = 2;
        graph[1][4] = 4;
        graph[2][3] = 2;
        graph[3][6] = 1;
        graph[4][5] = 3;
        graph[5][6] = 3;

        // 다익스트라 실행
        int[] result = dijkstra.dijkstra(n, start, graph);

        // 최단 거리 출력
        System.out.println("최단 거리:");
        for (int i = 1; i <= n; i++) {
            if (result[i] == INF) {
                System.out.println(i + " : 도달 불가");
            } else {
                System.out.println(i + " : " + result[i]);
            }
        }
    }
}

설명
1. `dijkstra` 메서드:
   - 입력: `n` (노드 수), `start` (출발 노드), `graph` (인접 행렬)
   - 출력: 출발 노드에서 각 노드까지의 최단 거리 배열
   - `dist[]` 배열을 사용하여 각 노드에 대한 최단 거리를 추적합니다.
   - 우선순위 큐(`PriorityQueue`)를 사용하여 최소 비용을 가진 노드를 우선적으로 처리합니다.

2. `PriorityQueue`:
   - `PriorityQueue<int[]>`에서 첫 번째 값은 노드이고, 두 번째 값은 현재까지의 최소 비용입니다.
   - 큐에서 가장 작은 비용을 가진 노드를 꺼내고, 그 노드와 연결된 노드들을 갱신합니다.

3. 결과:
   - `result[i]`는 출발 노드에서 노드 `i`로 가는 최소 비용을 나타냅니다.
   - 만약 `result[i]` 값이 `INF`이면, 해당 노드에는 도달할 수 없다는 의미입니다.

 

시간 복잡도
- 우선순위 큐를 사용한 다익스트라 알고리즘의 시간 복잡도는 O((V + E) * log V)입니다. 여기서 `V`는 노드의 수, `E`는 간선의 수입니다.
  - 각 노드에 대해 한 번씩 우선순위 큐에 삽입/삭제가 발생하므로, 시간 복잡도는 O(V * log V)입니다.
  - 또한, 각 간선에 대해 최소 비용을 갱신하므로 O(E * log V)가 추가됩니다.

 

다익스트라 알고리즘의 장점
- 최단 경로 문제 해결: 음의 가중치가 없는 그래프에서 매우 효율적으로 최단 경로를 구할 수 있습니다.
- 그리디 알고리즘: 각 노드를 처리할 때마다 가장 작은 비용을 우선적으로 처리하므로, 최적의 해를 구할 수 있습니다.

 

다익스트라 알고리즘의 단점
- 음의 가중치가 있을 경우 사용 불가: 음의 가중치를 가진 간선이 있을 경우 다익스트라 알고리즘은 동작하지 않습니다. 이 경우에는 벨만-포드 알고리즘을 사용해야 합니다. (참고: 벨만-포드 알고리즘)