[알고리즘] 다익스트라

원래 깃헙 블로그에 작성해뒀는데..... 블로그 이전 및 ICPC와 코딩테스트 준비하며 공부하는 내용을 다시 작성해보려고 한다.

Dijkstra(다익스트라) 알고리즘은 최단경로를 구하는 알고리즘으로 시작정점과 도착정점의 최단 경로를 구하는 알고리즘이다.

최단 경로문제는 만약 음의 가중치가 존재하지 않는다면 다익스트라 알고리즘을 사용하지만, 음의 가중치가 존재하면 벨만-포드 알고리즘을 사용한다. 하지만 이 글에선 다익스트라 알고리즘에 대해서만 작성하도록 하겠다.

다익스트라 알고리즘은 프림알고리즘의 원리와 비슷하다. 다익스트라 알고리즘은 정점 r에서 정점 v에 이르는 최단 거리를 위해 사용되고 프림알고리즘은 정점이 n개일때 n-1개의 간선을 모두 연결할때 가중치의 합이 가장 작은 트리를 구하는 차이가 있다.

프림알고리즘은 각 정점을 방문할 수 있는 가장 작은 가중치값을 저장한다면, 다익스트라 알고리즘에서는 각 정점에 방문할때 사용해야하는 가장 작은 가중치의합이 저장된다.

위의 그림처럼 시작정점을 기준으로 각 정점을 방문하는데 드는 가중치합을 각 정점에 저장해줌으로써, 1번정점에서 2번정점 / 1번정점에서 5번정점 등의 값을 구하고자 할때 그 정점에 저장된 가중치의 합들만 불러주면 된다.

 static void dijkstra(int start) {
        //우선 순위 큐 사용
        PriorityQueue<Node> q = new PriorityQueue<>((o1, o2) -> o1.cost - o2.cost);
        //시작 노드에 대해서 초기화
        q.add(new Node(start, 0));
        dist[start] = 0;

        while (!q.isEmpty()) {
            //최단 거리가 가장 짧은 노드
            Node now = q.poll();

            if (!visit[now.v]) {
                visit[now.v] = true;
            }

            for (Node next : graph[now.v]) {
                if (!visit[next.v] && dist[next.v] > now.cost + next.cost) {
                    dist[next.v] = now.cost + next.cost;
                    q.add(new Node(next.v, dist[next.v]));
                }
            }
        }
    }