다익스트라 알고리즘 : 하나의 출발점에서 다른 모든 출발지까지 최단 경로 계산

최단 경로 알고리즘은 간선의 가중치가 있는 그래프에서 두 정점 사이의 경로들 중 간선의 가중치 합이 최소인 경로를 찿는 알고리즘을 의미한다.

다익스트라 알고리즘

다익스트라 알고리즘은 특정한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로를 계산한다. 그리디 알고리즘으로 분류되며 매 상황에서 가장 비용이 적은 노드를 선택해 임의의 과정을 반복한다.

동작과정

1. 출발노드 설정
2. 최단 거리 테이블 초기화 ➜ 기본적으로 모든 노드까지 가는 비용을 무한으로 
3. 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드 선택
4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블 갱신
5. 위 과정에서 3번, 4번 반복

최단 거리 테이블은 각 노드에 대한 현재까지의 최단 거리 정보를 가지고 있기 때문에 더 짧은 경로를 찾으며 갱신한다.

 

방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드인 1번 노드(출발노드)를 처리한다. 1번 노드와 인접한 2번, 3번, 4번 노드와의 거리를 계산하여 테이블에 저장된 거리보다 짧을 경우 값을 갱신해준다. 이후 1번 노드는 처리한 노드 표시를 해준다.

방문하지 않은 노드 중 최단 거리가 가장 짧은 4번 노드를 처리한다. 4번 노드와 인접하면서 방문하지 않은 노드인 3번, 5번 노드와의 거리를 계산하여 테이블에 저장된 거리보다 짧을 경우 값을 갱신해준다. 이후 4번 노드도 방문처리 해준다. (반복)

단계를 거치며 한 번 처리된 노드의 최단 거리는 고정되어 더 이상 바뀌지 않는다.

우선순위 큐를 통한 다익스트라 구현

단계마다 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택하기 위해 힙(Heap) 자료구조를 이용한다. 현재의 최단 거리가 가장 짧은 노드를 선택해야 하므로 최소힙(min-Heap)을 이용한다.

class Node implements Comparable<Node> {
    int index;
    int distance;

    public Node(int index, int distance) {
        this.index = index;
        this.distance = distance;
    }

    @Override
    public int compareTo(Node o) {
        // 거리가 짧은 것이 높은 우선순위를 가지도록
        if (this.distance < o.distance)
            return -1;
        return 1;
    }
}

public static void dijkstra(int start) {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        // 출발노드를 큐에 삽입
        pq.offer(new Node(start, 0));
        d[start] = 0;
        while (!pq.isEmpty()) {
            // 최단 거리가 짧은 노드에 대한 정보 꺼내기
            Node node = pq.poll();
            int dist = node.distance;
            int now = node.index;
            // 현재 노드가 이미 처리된 적이 있는 노드라면 무시
            if (d[now] < dist) continue;
            // 현재 노드와 연결된 다른 인접한 노드들 확인
            for (int i = 0; i < graph.get(now).size(); i++) {
                int cost = d[now] + graph.get(now).get(i).distance;
                // 현재 노드를 거쳐서 다른 노드로 이동하는 거리가 더 짧은 경우
                if (cost < d[graph.get(now).get(i).index]) {
                    d[graph.get(now).get(i).index] = cost;
                    pq.offer(new Node(graph.get(now).get(i).index, cost));
                }
            }
        }

 

힙 자료구조를 이용하는 다익스트라 알고리즘의 시간복잡도는 O(ElogV) 가 된다. 현재 우선순위 큐에서 꺼낸 노드와 연결된 다른 노드들을 확인하는 총 횟수는 최대 간선의 개수(E)만큼 연산이 수행된다.