다익스트라(Dijkstra) 알고리즘

사이클 없는 양수 가중치 그래프에서 최단 거리를 구하는 알고리즘

 

시간 복잡도 : O(ElogV) (V : 노드 수, E : 에지 수)

 

📌 핵심 이론

 

문제

 

🔎 인접 리스트

 

다익스트라 알고리즘은 인접 행렬보다 시각 복잡도 측면, N의 크기가 클 것을 대비해 인접 리스트로 구현하는 것이 좋다.

 

인접 리스트

 

🔎 최단 거리 배열 초기화

 

최단 거리 값을 저장하기 위한 배열을 만든다. 출발 노드는 0, 나머지 노드는 매우 큰 값으로 초기화한다.

 

최단 거리 배열

 

🔎 값이 가장 작은 노드 고르기

 

최단 거리 배열에서 현재 값이 가장 작은 노드를 고른다. 따라서, 출발 노드에서 시작하면 된다.

 

🔎 최단 거리 배열 업데이트

 

인접 리스트와 최단 거리 배열 값을 비교하여 둘 중 작은 값으로 최단 거리 배열을 갱신한다.

 

Min(출발 노드의 최단 거리 배열의 값 + 가중치, 인접 노드의 최단 거리 배열의 값)

=> Min(현재 노드까지 온 거리 + 목적지 노드까지의 거리, 앞서 구해진 목적지 노드까지의 거리)

 

최단 거리 배열

 

🔎 모든 노드가 처리될 때까지 반복

 

최단 거리를 찾은 정점 중 거리가 가장 짧은 정점이 새로운 출발 노드가 되는데, 더 이상 이동할 곳이 없을 때까지 반복한다. 따라서, 도달할 수 없는 정점의
최단 거리 배열의 값은 매우 큰 값이 그대로 남는다.

 

다익스트라 알고리즘은
출발 노드와 도착 노드 간의 최단 거리(X)
출발 노드와 이외의 모든 노드 간의 최단 거리(O)

 

📌 구현

 

import java.io.IOException;
import java.util.*;

public class Main {

    static ArrayList<Edge>[] A; //인접 리스트
    static int[] dist; //최단 거리 배열 (1번 노드에서 각 노드까지의 최단 거리)

    public static void main(String[] args) throws IOException {
        int N = readInt();
        int M = readInt();
        A = new ArrayList[N + 1];
        dist = new int[N + 1];

        for (int i = 1; i <= N; i++) {
            A[i] = new ArrayList<>();
        }

        for (int i = 1; i <= N; i++) {
            dist[i] = Integer.MAX_VALUE; //최단 거리 배열 초기화
        }

        for (int i = 0; i < M; i++) {
            int s = readInt();
            int e = readInt();
            int w = readInt();
            A[s].add(new Edge(e, w)); //인접 리스트에 그래프 정보 저장
        }

        dijkstra();

        for (int i = 2; i <= N; i++) {
            if (dist[i] != Integer.MAX_VALUE)
                System.out.println(i + " : " + dist[i]);
            else
                System.out.println(i + " : impossible");
        }
    }

    static void dijkstra() {
        PriorityQueue<Edge> pq = new PriorityQueue<>(); //현재 구해진 최단 거리 정보
        dist[1] = 0; //1번 노드에서 각 정점까지의 거리
        pq.offer(new Edge(1, 0));
        while (!pq.isEmpty()) {
            Edge cur = pq.poll();
            int vex = cur.dst;
            int cost = cur.cost;
            if (cost > dist[vex]) continue; //더 큰 비용이 드는 경로
            for (Edge edge : A[vex]) { //vex 와 연결된 정점
                /**
                 * 기존의 최단 거리보다 적은 거리를 찾으면 갱신
                 * cost : 1번 노드에서 현재 정점(vex)까지의 거리
                 * edge.cost : 현재 정점에서 다음 정점(edge.dst)까지의 거리
                 * dist[edge.dst] : 이미 구해진 다음 정점까지의 최단 거리
                 **/
                if (cost + edge.cost < dist[edge.dst]) {
                    dist[edge.dst] = cost + edge.cost;
                    pq.offer(new Edge(edge.dst, cost + edge.cost));
                }
            }
        }
    }

    static class Edge implements Comparable<Edge> {
        int dst; //목적지
        int cost; //비용

        public Edge(int dst, int cost) {
            this.dst = dst;
            this.cost = cost;
        }

        @Override
        public int compareTo(Edge o) {
            return this.cost - o.cost; //비용 오름차순
        }
    }

    static int readInt() throws IOException {
        int c, n = System.in.read() & 15;
        while ((c = System.in.read()) > 32) n = (n << 3) + (n << 1) + (c & 15);
        return n;
    }

}

 

Reference:

 

https://www.inflearn.com/course/%EC%9E%90%EB%B0%94-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4-%EC%BD%94%ED%85%8C%EB%8C%80%EB%B9%84/dashboard

자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비 - 인프런 | 강의