다익스트라 알고리즘

다익스트라(Dijkstra)

시작점에서 다른 정점으로 가는 최단거리를 각각 구해주는 알고리즘이다.

음수 가중치가 있을 때의 최단거리는 다익스트라를 이용해서는 절대 구할 수 없다!

그래프 내의 정점의 수를 V, 간선의 수를 E라고 했을 때 이 알고리즘의 시간 복잡도는 O(ElogV)가 된다.

---

순서

1. 그래프에 있는 모든 노드들에 대해서 초기값을 전부 아주 큰 값(INF)로 설정한다.
2. 시작점에 대해서만 dist 값을 0으로 초기화한다.
3. 최소 힙(Java에서는 우선순위 큐(Priority Queue)로 구현)를 둠으로써 누적 최단 거리(dist)가 가장 작은 값을 빠르게 찾아낼 수 있다. 시작점만 먼저 넣는다. 
4. 우선순위 큐(pq)가 비어 있지 않을 때까지 반복한다.
   1. pq에서 Edge를 꺼낸다. pq의 정렬 기준이 dist 기준 오름차순이기 때문에, dist 값이 가장 작은 Edge를 선택하게 된다.
   2. 선택한 Edge와 연결된 Edge들을 전부 살펴보면서 값을 업데이트한다.
      1. 현재 최단 거리(dist[cur.to])에 가중치를 더한 값 expect가 기존 dist 값(dist[next.to])보다 더 작다면 dist 값을 갱신한다.
      2. pq에도 누적 거리를 업데이트한다.

---

JAVA로 구현하기

class Solution {
    static final int INF = Integer.MAX_VALUE;
    static List<Edge>[] graph; // 인접 리스트
    static int[] dist; // 시작 정점에서 i번 정점까지의 최단 거리
    
    public static void main(String[] args) {
        // dist 배열 초기화
        dist = new int[V];
        Arrays.fill(dist, INF);
        
        // 그래프 초기화
        graph = new ArrayList[V];
        for (int i=0; i<V; i++)
            graph[i] = new ArrayList<>();
        // 그래프 정보가 주어짐

        dijkstra(start);
        
        return;
    }

    static void dijkstra(int start) {
        // pq는 i점까지 가는 총 비용이 작은 순으로 정렬하는 것을 의미(최단거리)
        PriorityQueue<Node> pq = new PriorityQueue<>(Comparator.comparingInt(e -> e.dist));
        pq.offer(new Edge(start, 0));
        dist[start] = 0;
        
        while (!pq.isEmpty()) {
            Edge cur = pq.poll();
            
            // 이미 알고 있는 최단거리가 가중치보다 크면 패스
            if (dist[cur.to] < cur.weight) continue;
            
            // 연결된 간선을 탐색
            for (Edge next : graph[cur.to]) {
                // 예상되는 값은 현재 알고 있는 최단거리 + 가중치
                int expect = dist[cur.to] + next.weight;
                // 예상되는 값이 갈 곳의 최단거리보다 작으면 최단 거리를 갱신 + pq에 누적
                if (expect < dist[next.to]) {
                    dist[next.to] = expect;
                    pq.offer(new Edge(next.to, expect));
                }
            }
        }
        return dist;
    }
}

class Edge {
    int to, weight; // 목적지, 가중치
    
    Edge(int to, int distance) {
        this.to = to;
        this.distance = distance;
    }
}