개선된 다익스트라 알고리즘

static void dijkstra(int start) {
        Queue<Node> q = new PriorityQueue<>();
        q.offer(new Node(start,0));
        distance[start] = 0;
        while(!q.isEmpty()) {
            Node shortest = q.poll();
            int dist = shortest.distance;
            int now = shortest.index;

            if (distance[now] < dist) {
                continue;
            }

            for(int i = 0; i<graph.get(now).size();i++) {
                int cost = dist + graph.get(now).get(i).distance;

                if (cost < distance[graph.get(now).get(i).index]) {
                    distance[graph.get(now).get(i).index] = cost;
                    q.offer(new Node(graph.get(now).get(i).index,cost));
                }
            }
        }
    }

 

기본적인 다익스트라 알고리즘과 달리 두드러지는 차이점한가지 있다.

 바로 순회 방식을 사용했는가 아니면.... 우선순위 큐를 사용했는가라는 차이가 있다.

결론부터 말하면 우선순위 큐를 사용하는 것이 더 빠르다고 한다.

어차피 코드는 같으니 설명은 하지는 않는다.

왜 우선순위 큐가 사용하는 것이 더 시간복잡도가 작은 이유는.

힙을 이용하기 때문이다. 힙은 

 가장 위를 level1 그다음은 level2... 이런식으로 진행하면 총 level은 3이 나온다.

즉, 힙을 사용하게 된다면 3번의 연산으로 해결할 수 있다는 뜻이 된다.

level에 따라 시간이 달라지기 때문에 순회보다 더 효율적이라 할 수 있다.

결국.... 각각의 노드별로 우선순위 큐가 돌아가기 때문에

O(ElogV)가 된다.

 if (distance[now] < dist) {
                continue;
}

 

이 부분이 조금 의아할 수 있다.
어차피 최솟값을 찾는 것이기때문에 큐에서 뺀값이 저장된 값보다 크다면? 굳이 다음 코드를 동작할 이유가 없다.

그렇기 때문에 continue를 붙인것이다. 이건 기본 다이스트라 알고리즘에서 visited를 담당한다.