알고리즘) 다익스트라 알고리즘(가중치 방향 그래프)

주요 개념 ✨

가중치 방향 그래프

방향을 지닌 그래프로, 각 edge에 가중치를 가진다.

다익스트라 알고리즘

특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알려주는 알고리즘이다. 가중치 방향 그래프에서 다익스트라 알고리즘을 이용할 때는 간선의 가중치가 음수이면 안되는 점을 유의해야 한다. (0은 될 수 있다.)

문제 ✨

 가중치 방향그래프에서 1번 정점에서 모든 정점으로의 최소비용을 출력하시오. (2번 정점부터 출력)

풀이 ✨

 메모이라이즈할 배열 변수를 두어 1부터 각 노드로의 거리비용을 저장한다. 해당 배열에 해당 노드의 거리비용 값이 있는 경우 새로운 값이 더 작을 때에만 그 값을 대체한다. 이 때 문제는 N개의 노드를 대상으로 각 노드로의 거리 비용을 구하기 위해서는 ${n}*{n}$만큼 반복되어야 한다. 시간 효율성을 줄이기 위해서는 이진 트리로 구성된 우선순위큐를 사용해 ${n}log(n)$만큼 반복되도록 줄일 수 있다.

작성 코드

import java.util.*;

// 다익스트라 알고리즘
// 1번 노드에서 n - 1개의 노드(2부터 시작)까지의 최단 거리 구하기
public class Main {
    static int n;
    static int m;
    static List<ArrayList<Edge>> list = new ArrayList<ArrayList<Edge>>();
    static int[] dist;

    static class Edge implements Comparable<Edge> {
        int vertex; // 꼭짓점
        int cost; // 가중치(비용)

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

        public int compareTo(Edge e) {
            return this.cost - e.cost; // 가중치가 적은 것을 먼저 poll 하도록 함
        }
    }

    void solution() {
        PriorityQueue<Edge> queue = new PriorityQueue<>();
        queue.offer(new Edge(1, 0)); // 1번 노드에서 시작
        dist[1] = 0;
        while (!queue.isEmpty()) {
            Edge e = queue.poll();
            int curr = e.vertex;
            int currCost = e.cost;

            if (currCost > dist[curr]) continue; // 이미 메모이라이즈한 값보다 클 경우에는 굳이 할 필요가 없음.
            for (Edge obj : list.get(curr)) {
                if (dist[obj.vertex] > currCost + obj.cost) { // dist[i]가 Integer.MAX_VALUE일 때에는 currCost가 더 클 수 없음을 이용
                    dist[obj.vertex] = currCost + obj.cost; // 메모이라이즈한 값을 더 작은 값으로 대체
                    queue.offer(new Edge(obj.vertex, currCost + obj.cost)); // 다른 노드로의 이동에 사용할 수 있게 현재 노드와 현재까지의 가중치를 큐에 저장
                }
            }
        }
    }

    public static void main(String[] args) {
        Main main = new Main();
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt(); // node size
        m = sc.nextInt(); // edge size
        dist = new int[n + 1];
        Arrays.fill(dist, Integer.MAX_VALUE); // 최솟값으로 대체하기 위해 해당 배열의 모든 인덱스에 최댓값을 넣음
        for (int i = 0; i <= n; i++) list.add(new ArrayList<>()); // node number와 index가 일치할 수 있게 0부터 넣음
        for (int i = 0; i < m; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            int c = sc.nextInt();
            list.get(a).add(new Edge(b, c));
        }

        main.solution();
        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");
        }
    }
}
```