[알고리즘] *다익스트라 알고리즘

다익스트라 알고리즘이 뭘까?

다익스트라 알고리즘이란

하나의 출발점에서 도달할 수 있는 모든 도착점에 대한 최단 경로를 구할 수 있는 알고리즘이다. 

대신 조건이 있는데 다익스트라 알고리즘은 간선들의 비용이 모두 양수여야만 적용이 가능하다. 만약 음의 비용을 가진 간선이 존재한다면 최단 경로를 구할 수 없다. 

다익스트라 알고리즘과 다이나믹 프로그래밍

다익스트라 알고리즘의 메인 아이디어는 다이나믹 프로그래밍(DP)이다. 다익스트라 알고리즘은 기존에 구해놓은 최단 거리를 이용하여 최단 거리를 갱신해나가는 메인 아이디어를 가지고 있다. (최단 경로는 최단 경로들의 집합으로 이루어져 있다)

다익스트라 알고리즘의 복잡도 (좀 더 자세히 알아볼 것)

원래 다익스트라 알고리즘은 O(V^2)의 시간 복잡도를 가지고 있었지만 우선순위 큐를 활용한 발전된 아이디어가 제공되면서 O(E * lgV)의 시간복잡도를 가진 알고리즘으로 개선되었다.  (V는 노드의 수, E는 간선의 수) 

 

다익스트라 알고리즘 로직 

1. 시작 노드를 선택하여, 우선 순위큐에 삽입한다. 

   1-1. 시작 노드의 최단 경로를 0으로 초기화 하고, 나머지 노드는 무한대 값으로 초기화한다. 

2. 우선 순위 큐(Min Heap)에서 가장 작은 비용을 가진 노드를 꺼낸다.

  2-1. 꺼낸 노드와 연결된 노드들을 가져와 반복한다.

    2-1-1. u가 출발 노드 v가 목적지라고 할 때, 최단 경로 비용[v] = Math.min(최단 경로 비용[v], 최단 경로 비용[u] + 경로 비용[u][v]) (s -> v, s -> u -> v) 을 비교하는 것

3. 2번을 우선 순위 큐에 노드가 존재하지 않을 때 까지 반복한다. 

 

다익스트라 알고리즘 구현

    private void dijkstra(int start) {
        boolean[] check = new boolean[adjArray.length+1];
        PriorityQueue<int[]> queue = new PriorityQueue<>(Comparator.comparingInt(o -> o[1]));

        Arrays.fill(distance, Integer.MAX_VALUE);
        distance[start] = 0;

        queue.add(new int[]{start, 0});
        while(!queue.isEmpty()) {
            int[] u = queue.poll();
            if(distance[u[0]] < u[1]) continue;;
            LinkedList<Integer> connectedNodes = findConnectedNode(u[0]);
            for(int v : connectedNodes) {
                if(distance[v] > distance[u[0]] + adjArray[u[0]][v]) {
                    distance[v] =  distance[u[0]] + adjArray[u[0]][v];
                    queue.add(new int[]{v, distance[v]});
                }
            }
        }
    }

    private LinkedList<Integer> findConnectedNode(int u) {
        LinkedList<Integer> connectedNodes = new LinkedList<>();
        int[] adjLine = adjArray[u];
        for(int i=1; i<adjLine.length; i++) {
            if(adjLine[i] != 0) connectedNodes.add(i);
        }
        return connectedNodes;
    }

 Q1. if(distance[u[0]] < u[1])) continue; 는 왜 하는걸까요? 

다익스트라 알고리즘의 메인 아이디어는 기존의 최단 경로를 활용하여 최단 경로를 구하는 로직인데, 최단 경로가 아니라면 굳이 그것을 이용하여 갱신을 시도할 필요가 없기 때문에 하는겁니다.

Q2. if(distance[v] > distance[u[0]] + adjArray[u[0]][v]) 여야 queue에 노드를 넣는건가요? 

위의 질문의 대답처럼 최단 경로를 이용하여 새로운 최단 경로를 구하는 로직인데, 갱신이 되지 않은 (최소가 아닌) 경로를 활용할 필요는 없기 때문입니다.