Dijkstra - 다익스트라

다익스트라 알고리즘은 최단경로를 구하는 알고리즘이다.

💡 최단경로 ➡ 정점 i에서 정점 j를 연결하는 경로 중 가중치의 합이 최소인 경로

정의

• 하나의 시작정점으로부터 모든 다른 정점까지의 최단 경로를 찾는 알고리즘
• 동적 프로그래밍 활용 ➡ 최단 거리는 여러 개의 최단거리로 이루어져 있다.
• 간선의 가중치가 음수일 경우 사용 불가

접근

• 특정 위치에서 특정 위치까지의 최단거리를 구하는 문제에 사용

구현

변수

• 인접행렬, 인접리스트 ➡ 그래프 정보 표현
• distance[] ➡ 시작 정점에서 특정 정점까지의 경로의 최소를 저장하는 배열
• visited[] ➡ 배열 방문 체크

알고리즘

1. distance[]의 값을 무한대로 초기화
2. 시작 정점의 거리 0 ➡ distance[시작 정점] = 0
3. 시작 정점과 인접한 노드에 대해 distance값 갱신
4. 방문하지 않은 노드 중 distance값이 최소인 정점 찾기
   • 인접한 정점 중 최소인 간선을 찾기
5. 최소인 정점 방문
6. 최소인 정점과 연결된 노드 가운데 아래 식을 만족하면 distance 초기화

   if (distance[현재노드] + 연결된노드의 가중치 < distnace[연결된노드]) 
           distance[연결된노드] = distance[현재노드] + 연결된노드의 가중치;

7. 모든 정점을 방문할 때까지 반복
8. 최종 distance[] ➡ 시작 정점으로부터 각 정점까지의 최단거리

예

• distance[] 선언 및 초기화
• 0번 노드에서 다른 노드로 가는 가중치
• 인정행렬의 값으로 초기화

0	1	2	3	4	5	6
0	7	∞	∞	3	10	∞

• distance[]값이 최소인 4와 인접한 노드에 대해 distance값 갱신

0	1	2	3	4	5	6
0	5	∞	14	3	10	8

• 1과 인접한 노드에 대해 distance값 갱신

0	1	2	3	4	5	6
0	5	9	14	3	10	8

• 6과 인접한 노드에 대해 distance값 갱신

0	1	2	3	4	5	6
0	5	9	12	3	10	8

• 2와 인접한 노드에 대해 distance값 갱신

0	1	2	3	4	5	6
0	5	9	11	3	10	8

• 5와 인접한 노드에 대해 distance값 갱신

0	1	2	3	4	5	6
0	5	9	11	3	10	8

코드

distance 배열에서 아직 방문하지 않았고 가중치가 가장 작은 노드를 선택할 때 우선순위 큐를 사용하면 시간복잡도가 꽤 줄어든다.

// 우선순위큐, 인접리스트
public class Dijkstra {
    static int V, E, START;

    static class Node implements Comparable<Node> {
        int node, weight;

        public Node(int node, int weight) {
            this.node = node;
            this.weight = weight;
        }

        @Override
        public int compareTo(Node node) {
            return this.weight - node.weight;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        V = Integer.parseInt(st.nextToken());
        E = Integer.parseInt(st.nextToken());
        START = Integer.parseInt(br.readLine()) - 1;    // 시작정점

        ArrayList<LinkedList<Node>> graph = new ArrayList<>(V); // 인접리스트
        for (int i = 0; i < V + 1; i++) {
            graph.add(new LinkedList<>());
        }

        for (int i = 0; i < E; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken()) - 1;
            int end = Integer.parseInt(st.nextToken()) - 1;
            int weight = Integer.parseInt(st.nextToken());
            graph.get(start).add(new Node(end, weight));
        }

        // 1. distance를 무한대로 초기화
        PriorityQueue<Node> pq = new PriorityQueue<>();
        int[] distance = new int[V];
        Arrays.fill(distance, Integer.MAX_VALUE);
        boolean[] visited = new boolean[V];

        // 2. 시작노드의 거리를 0으로
        pq.offer(new Node(START, 0));
        distance[START] = 0;

        // 3. 시작노드와 인접한 노드들의 distance값 갱신
        graph.get(START)
                .forEach(node -> pq.offer(new Node(node.node, node.weight)));
        for (Node node : graph.get(START)) {
            distance[node.node] = node.weight;
        }

        while (!pq.isEmpty()) { // 모든 노드를 방문할 때까지 반복
            // 4. 방문하지 않은 노드 중 distance 값이 최소인 정점을 찾음
            // 5. 최소인 정점을 방문
            Node curNode = pq.poll();

            // 방문했는지 체크
            if (visited[curNode.node]) continue;
            visited[curNode.node] = true;

            // 최소인 정점과 연결된 정점들의 distance 갱신
            for (Node node : graph.get(curNode.node)) {
                if (distance[curNode.node] + node.weight < distance[node.node]) {
                    distance[node.node] = distance[curNode.node] + node.weight;
                    pq.offer(new Node(node.node, distance[node.node]));
                }
            }
        }

        // 출력
        StringBuilder sb = new StringBuilder();
        Arrays.stream(distance)
                .forEach(v -> {
                    if (v == Integer.MAX_VALUE) {
                        sb.append("INF").append("\n");
                    } else {
                        sb.append(v).append("\n");
                    }
                });
        System.out.println(sb);
    }

연습문제

1753번: 최단경로