최단 경로 알고리즘 (1): 다익스트라 알고리즘 (Dijkstra's Algorithm)

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

다익스트라 알고리즘(Dijkstra's Algorithm)은 양수 가중치를 가진 그래프에서 한 정점에서 다른 모든 정점까지의 최단 경로를 찾는 알고리즘이다.

1.1 다익스트라 알고리즘의 특징

• 비용 최소화: 출발점에서 각 정점까지의 최소 비용 경로 탐색
• 양수 가중치 그래프에서 사용 가능: 음수 가중치는 허용되지 않음
• 우선순위 큐 사용 시 효율적: 시간 복잡도 O((V + E) log V)

2. 다익스트라 알고리즘의 동작 원리

다익스트라 알고리즘은 다음과 같은 단계로 동작한다:

1. 초기화:
   • 출발 노드의 거리를 0으로 설정하고, 나머지 노드는 무한대로 초기화
   • 방문하지 않은 모든 노드를 저장하는 우선순위 큐 생성
2. 최단 경로 갱신:
   • 현재 노드에서 인접한 노드로 가는 비용을 계산
   • 계산한 비용이 기존 값보다 작으면 최단 거리 갱신
3. 노드 선택:
   • 방문하지 않은 노드 중 최단 거리의 노드를 선택하고 방문 처리
4. 반복:
   • 모든 노드를 방문하거나, 더 이상 최단 경로를 갱신할 수 없을 때까지 반복

2.1 다익스트라 알고리즘 예제

다음과 같은 그래프에서 노드 0에서 시작해 각 노드까지의 최단 경로를 구한다고 하자.

        (0)
      /  |  \
    4   2   5
   (1) (2) (3)
    \    |   |
     6   1   3
      \  |  /
       (4)

2.2 다익스트라 알고리즘의 수행 과정

1. 출발 노드(0)의 거리를 0으로 설정하고, 나머지 노드는 ∞로 설정
2. 우선순위 큐에서 거리가 가장 작은 노드를 선택 (초기: 0)
3. 인접한 노드의 거리를 갱신 (0 → 1, 2, 3)
4. 큐에서 다음으로 가장 가까운 노드를 방문
5. 모든 노드를 방문할 때까지 반복

3. 다익스트라 알고리즘 구현 (Java)

import java.util.*;

class Node implements Comparable<Node> {
    int vertex;
    int cost;

    Node(int vertex, int cost) {
        this.vertex = vertex;
        this.cost = cost;
    }

    @Override
    public int compareTo(Node other) {
        return Integer.compare(this.cost, other.cost);
    }
}

public class Dijkstra {
    public static void dijkstra(Map<Integer, List<Node>> graph, int start) {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        Map<Integer, Integer> distances = new HashMap<>();

        for (int vertex : graph.keySet()) {
            distances.put(vertex, Integer.MAX_VALUE);
        }
        distances.put(start, 0);

        pq.add(new Node(start, 0));

        while (!pq.isEmpty()) {
            Node current = pq.poll();

            if (current.cost > distances.get(current.vertex)) continue;

            for (Node neighbor : graph.get(current.vertex)) {
                int newDistance = distances.get(current.vertex) + neighbor.cost;

                if (newDistance < distances.get(neighbor.vertex)) {
                    distances.put(neighbor.vertex, newDistance);
                    pq.add(new Node(neighbor.vertex, newDistance));
                }
            }
        }

        for (Map.Entry<Integer, Integer> entry : distances.entrySet()) {
            System.out.println("노드 " + entry.getKey() + "까지의 최단 거리: " + entry.getValue());
        }
    }

    public static void main(String[] args) {
        Map<Integer, List<Node>> graph = new HashMap<>();

        graph.put(0, Arrays.asList(new Node(1, 4), new Node(2, 2), new Node(3, 5)));
        graph.put(1, Arrays.asList(new Node(4, 6)));
        graph.put(2, Arrays.asList(new Node(4, 1)));
        graph.put(3, Arrays.asList(new Node(4, 3)));
        graph.put(4, new ArrayList<>());

        dijkstra(graph, 0);
    }
}

4. 다익스트라 알고리즘의 성능 분석

4.1 시간 복잡도

• 인접 리스트 + 우선순위 큐 사용: O((V + E) log V)
• 인접 행렬 사용: O(V²)

4.2 공간 복잡도

• O(V + E): 그래프 저장, 우선순위 큐, 거리 배열

5. 다익스트라 알고리즘의 장점과 단점

5.1 장점

• 양수 가중치 그래프에서 효율적
• 우선순위 큐 활용으로 빠른 탐색 가능
• 경로 추적이 용이

5.2 단점

• 음수 가중치가 있는 경우 오작동 (벨만-포드 알고리즘 사용 필요)
• 그래프의 크기가 매우 클 경우 메모리 사용량 증가

6. 다익스트라 알고리즘의 활용 사례

• 지도 및 경로 탐색: 네비게이션 시스템에서 최단 경로 계산
• 네트워크 최적화: 데이터 전송 최적화
• AI 및 게임: 캐릭터 이동 경로 계산
• 통신: 패킷 전송 시 최적 경로 탐색

7. 다익스트라 알고리즘 vs. 벨만-포드 알고리즘

특징	다익스트라 알고리즘	벨만-포드 알고리즘
시간 복잡도	O((V + E) log V)	O(V × E)
음수 가중치	❌ 허용하지 않음	✅ 허용
구현 복잡도	보통 (우선순위 큐 활용)	단순 (반복문 기반)
적용 분야	양수 가중치의 그래프	음수 가중치 포함한 경로 탐색

8. 결론

다익스트라 알고리즘은 양수 가중치를 가진 그래프에서 최단 경로를 찾는 강력한 알고리즘으로, 지도 탐색, 네트워크 최적화 등 다양한 분야에서 활용된다. 음수 가중치가 포함된 경우에는 벨만-포드 알고리즘을 사용해야 한다. 문제의 특성과 그래프의 형태에 따라 적절한 알고리즘을 선택하는 것이 중요하다.