최단 경로 문제 (다익스트라)

최단 경로 문제란?

• 최단 경로란 두 노드를 잇는 가장 짧은 경로를 찾는 문제
• 가중치 그래프에서 간선의 가중치 합이 최소가 되도록 하는 경로를 찾는 것이 목적

최단 경로 문제 예시

1. 단일 출발 및 단일 도착 최단 경로 문제
   • u → v 에 도착하는 가장 짧은 경로를 찾는다.
2. 단일 출발 최단 경로 문제
   • 그래프 내의 특정 노드 u와 그래프 내 다른 모든 노드 각각의 가장 짧은 경로를 찾는 문제
3. 전체 쌍 최단 경로 문제
   • 그래프 내의 모든 노드 쌍 (u, v)에 대한 최단 경로를 찾는 문제

이제 최단 경로 문제를 풀 때 사용하는 알고리즘에 대해 알아보자.

다익스트라

다익스트라는 위에 문제 예시에서 2번째에 해당한다.

• 하나의 정점에서 다른 모든 정점 간의 각각 가장 짧은 거리를 구하는 문제

가장 보편화되어 있는 방식은 우선순위 큐를 활용하는 방식이다.

1. 첫 정점을 기준으로 배열을 선언하여 첫 정점에서 각 정점까지의 거리를 저장
   • 초기에는 첫 정점의 거리는 0, 나머지는 무한대(INF)로 저장한다.
   • 우선순위 큐에 (첫 정점, 거리 0)[EDGE 클래스 선언] 만 먼저 넣음.
2. 우선순위 큐에서 노드를 꺼냄
   • 꺼낸 정점에 인접한 노드들 각각에 대해, 첫 정점에서 각 노드로 가는 거리와 현재 배열에 저장되어 있는 거리를 비교한다.
   • 배열에 저장되어 있는 거리보다, 첫 정점에서 해당 노드로 가는 거리가 더 짧을 경우, 배열에 해당 노드의 거리를 업데이트한다.
   • 배열에 해당 노드의 거리가 업데이트된 경우, 우선순위 큐에 넣는다.
3. 우선순위 큐에 꺼낼 노드가 없을 때까지 반복한다.

다익스트라 예시 코드

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

public class Main {

    static int N;
    static List<Edge> map[];
    static int[] distances; // 최단거리

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.valueOf(st.nextToken());
        int dependencyCount = Integer.valueOf(st.nextToken());
        int infectiousComputer = Integer.valueOf(st.nextToken());

        map = new ArrayList[N + 1];

        // 초기 거리는 무한대(INF)로 지정
        distances = new int[N + 1];
        Arrays.fill(distances, Integer.MAX_VALUE);

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

        for (int i = 0; i < dependencyCount; i++) {
            st = new StringTokenizer(br.readLine());
            int from = Integer.valueOf(st.nextToken());
            int to = Integer.valueOf(st.nextToken());
            int time = Integer.valueOf(st.nextToken());
            map[to].add(new Edge(from, time));
        }
        // 다익스트라 시작
        dijkstra(infectiousComputer);
        int cnt = 0;
        int time = 0;
        for (int i = 1; i <= N; i++) {
            if (distances[i] != Integer.MAX_VALUE) {
                cnt++;
                time = Math.max(time, distances[i]);
            }
        }
    }

    private static class Edge implements Comparable<Edge> {
        private int from;
        private int time;

        Edge(int from, int time) {
            this.from = from;
            this.time = time;
        }

        // 최단 경로를 위해 compareTo를 오버라이드해준다.
        @Override
        public int compareTo(Edge o) {
            return this.time - o.time;
        }
    }

    private static void dijkstra(int infectiousComputer) {
        PriorityQueue<Edge> queue = new PriorityQueue<>();
        // 첫 정점의 거리는 0으로 설정
        distances[infectiousComputer] = 0;
        // 첫 정점과 0을 우선순위 큐에 넣어준다.
        queue.add(new Edge(infectiousComputer, 0));

        while (!queue.isEmpty()) {
            Edge Edge = queue.poll();
            int standardNode = Edge.from; // 기준 노드
            int time = Edge.time; // 첫 정점에서 기준 노드와의 거리
            if (distances[standardNode] < time) {
                continue;
            }

            List<Edge> anotherEdges = map[standardNode]; // 기준 노드에 연결된 노드들의 리스트
            for (Edge anotherEdge : anotherEdges) {
                int nextFrom = anotherEdge.from; // 해당 노드
                /**
                 * anotherEdge.time - 기준 노드 ~ 해당 노드 거리
                 * time : 첫 정점 노드 ~ 기준 노드
                 * 따라서, nextTime은 첫 정점 노드 ~ 기준 노드 ~ 해당 노드 거리
                 */
                int nextTime = anotherEdge.time + time;

                // 첫 정점에서 해당 노드와의 거리(distances[nextFrom]과 nextTime을 비교 후 업데이트
                if (distances[nextFrom] > nextTime) {
                    distances[nextFrom] = nextTime;
                    // 우선순위 큐에 넣어준다.
                    queue.add(new Edge(nextFrom, nextTime));
                }
            }
        }
    }
}

대표 문제

• [ ] 특정 거리의 도시 찾기
• [ ] 최단경로
• [ ] 최소비용 구하기
• [ ] 파티
• [ ] 알고스팟
• [ ] 특정한 최단 경로
• [ ] 숨바꼭질 3
• [ ] 녹색 옷 입은 애가 젤다지?
• [ ] 최소비용 구하기 2