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

반응형
반응형
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를 담당한다.

 

반응형

댓글

Designed by JB FACTORY