[알고리즘/그래프] 다익스트라 알고리즘(Dijkstra Algorithm)

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

---

이미지 출처 첨부

그리디 알고리즘/다이나믹 프로그래밍을 이용한 대표적인 그래프의 최단 경로(Shortest Path)를 구하는 알고리즘이다. 다익스트라 알고리즘은 음의 가중치가 없는 그래프의 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 구한다.

 

다익스트라 알고리즘은 하나의 최단 거리를 구할 때 이전에 구했던 최단 거리 정보를 그대로 사용한다. 최단 거리는 여러개의 최단거리로 이루어져있다고 볼 수 있다. 따라서 다익스트라 알고리즘은 다이나믹 프로그래밍 기법을 사용한다.

 

* 인공 위성 GPS에 가장 많이 사용된다.

 

그래프의 최단 경로를 구하는 알고리즘 비교

알고리즘	특징
BFS	간선의 가중치가 모두 같은 그래프의 경우
다익스트라 알고리즘(Dijkstra Algorithm)	간선의 가중치가 다르고 음의 간선이 존재하지 않는 그래프의 경우, 하나의 정점에서 모든 정점으로의 최단 거리를 구하는 경우
벨만-포드 알고리즘(Bellman–Ford Algorithm)	간선의 가중치가 다르고 음의 간선이 존재하는 그래프의 경우
플로이드 와샬 알고리즘(Floyd–Warshall Algorithm)	모든 정점에서 다른 모든 정점까지의 최단거리를 구하는 경우

구현 방법

1. 출발 노드와 도착 노드를 정한다.
2. 최단 거리 테이블을 초기화한다.
3. 현재 방문한 노드의 인접 노드중 방문하지 않은 노드를 식별하고 방문하지 않은 노드중에서 가장 거리가 짧은 노드를 선택한다. (그리디 알고리즘)
4. 해당 노드를 방문처리한다.
5. 해당 노드로부터 방문할 수 있는 노드들의 가중치를 계산해서 최단 거리 테이블을 업데이트한다. (다이나믹 프로그래밍)
6. 3~5번을 반복한다.

구현 코드

인접 행렬 혹은 우선 순위 큐를 이용하여 다익스트라 알고리즘을 구현할 수 있다.

1) 인접 행렬 이용

인접 행렬을 사용하는 경우 선형 탐색을 하여 최소 비용을 탐색한다. 따라서 O( N^2 )의 시간 복잡도를 가지게 된다. 또한 정점의 개수가 많으나 간선의 개수가 적은 그래프의 경우 매우 비효율적으로 동작할 수 있다.

• 시간 복잡도:  O( N^2 )

public class AdjacentListDijkstra {

    static final int INF = 9999999; // 무한대

    static class Node implements Comparable<Node> {
        int to, weight;

        public Node(int to, int weight) {
            this.to = to;
            this.weight = weight;
        }

        @Override
        public int compareTo(Node o) {
            return this.weight - o.weight;
        }
    }

    public static void main(String[] args) {
        int V = 5;  // 정점의 수
        int E = 6;  // 간선의 수

        // 인접리스트 초기화
        ArrayList<ArrayList<Node>> adjList = new ArrayList<>();
        for (int i = 0; i <= V; i++) {
            adjList.add(new ArrayList<>());
        }

        // 인접리스트 입력
        adjList.get(5).add(new Node(1, 1));
        adjList.get(1).add(new Node(5, 1));

        adjList.get(1).add(new Node(2, 2));
        adjList.get(2).add(new Node(1, 2));

        adjList.get(1).add(new Node(3, 3));
        adjList.get(3).add(new Node(1, 3));

        adjList.get(2).add(new Node(3, 4));
        adjList.get(3).add(new Node(2, 4));

        adjList.get(2).add(new Node(4, 5));
        adjList.get(4).add(new Node(2, 5));

        adjList.get(3).add(new Node(4, 6));
        adjList.get(4).add(new Node(3, 6));


        int[] dist = new int[V + 1]; // 최단 거리 저장
        Arrays.fill(dist, INF); // 무한대로 초기화
        dist[1] = 0; // 시작 노드 초기화
        boolean[] visited = new boolean[V + 1];  // 노드 방문 여부 저장

        for (int i = 1; i <= V; i++) {
            int nodeValue = Integer.MAX_VALUE;
            int nodeIdx = 0;

            // 인접 노드의 최단 거리 갱신
            for (int j = 1; j < V + 1; j++) {
                if (!visited[j] && dist[j] < nodeValue) {
                    nodeValue = dist[j];
                    nodeIdx = j;
                }
            }

            // 방문 처리
            visited[nodeIdx] = true;

            // 다른 노드를 거쳐가는 비용이 더 적은지 확인
            for (Node n : adjList.get(nodeIdx)) {
                if (dist[n.to] > dist[nodeIdx] + n.weight) {
                    dist[n.to] = dist[nodeIdx] + n.weight;
                }
            }
        }

        // 결과 출력
        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= V; i++) {
            sb.append(dist[i]).append(" ");
        }
        System.out.println(sb);
    }
}

 

2) 우선 순위 큐 이용

우선 순위 큐를 사용하는 경우 힙 구조를 활용하여 시간 복잡도를 O( V log V )으로 낮출 수 있다. 힙구조를 활용하여 우선 순위 큐를 구현한다.

• 시간 복잡도:  O( N log N)

public class PriorityQueueDijkstra {

    static final int INF = 9999999; // 무한대

    static class Node implements Comparable<Node> {
        int to, weight;

        public Node(int to, int weight) {
            this.to = to;
            this.weight = weight;
        }

        @Override
        public int compareTo(Node o) {
            return this.weight - o.weight;
        }
    }

    public static void main(String[] args) {
        int V = 5;  // 정점의 수
        int E = 6;  // 간선의 수

        // 인접리스트 초기화
        ArrayList<ArrayList<Node>> adjList = new ArrayList<>();
        for (int i = 0; i <= V; i++) {
            adjList.add(new ArrayList<>());
        }

        // 인접리스트 입력
        adjList.get(5).add(new Node(1, 1));
        adjList.get(1).add(new Node(5, 1));

        adjList.get(1).add(new Node(2, 2));
        adjList.get(2).add(new Node(1, 2));

        adjList.get(1).add(new Node(3, 3));
        adjList.get(3).add(new Node(1, 3));

        adjList.get(2).add(new Node(3, 4));
        adjList.get(3).add(new Node(2, 4));

        adjList.get(2).add(new Node(4, 5));
        adjList.get(4).add(new Node(2, 5));

        adjList.get(3).add(new Node(4, 6));
        adjList.get(4).add(new Node(3, 6));

        int[] dist = new int[V + 1]; // 최단 거리 저장
        Arrays.fill(dist, INF); // 무한대로 초기화
        dist[1] = 0; // 시작 노드 초기화
        boolean[] visited = new boolean[V + 1];  // 노드 방문 여부 저장

        PriorityQueue<Node> pq = new PriorityQueue<>(); // 노드까지의 거리를 저장할 우선순위 큐
        pq.offer(new Node(1, 0)); // 시작노드 값 초기화
        
        // 인접 노드의 최단 거리 갱신
        while (!pq.isEmpty()) {
            Node current = pq.poll();

            if (visited[current.to]) continue;
            
            // 방문 처리
            visited[current.to] = true;

            // 다른 노드를 거쳐가는 비용이 더 적은지 확인
            for (Node n : adjList.get(current.to)) {
                if (!visited[n.to] && dist[n.to] > dist[current.to] + n.weight) {
                    dist[n.to] = dist[current.to] + n.weight;
                    pq.offer(n);
                }
            }
        }

        // 결과 출력
        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= V; i++) {
            sb.append(dist[i]).append(" ");
        }
        System.out.println(sb.toString());
    }

}