다익스트라 알고리즘

다익스트라(Dijkstra) 알고리즘은 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 구하는 알고리즘이다. 이 알고리즘은 우선순위 큐를 사용하여, 각 정점까지의 최단 경로를 빠르게 계산할 수 있다.

 

문제 설명

주어진 그래프에서 1번 정점에서 모든 다른 정점으로의 최소 거리 비용을 구하고, 그 결과를 출력하는 프로그램을 작성해야 한다. 만약 특정 정점으로 가는 경로가 존재하지 않으면 impossible을 출력한다.

입력 설명

• 첫 번째 줄에 정점의 수 N(1<=N<=20)와 간선의 수 M이 주어진다.
• 다음 M개의 줄에 각 간선 정보(출발 정점, 도착 정점, 거리 비용)가 주어진다.

출력 설명

1번 정점에서 2번 정점부터 차례대로 각 정점까지의 최단 거리를 출력한다. 만약 특정 정점으로 갈 수 없는 경우는 impossible을 출력한다.

 

입력 예제

6 9
1 2 12
1 3 4
2 1 2
2 3 5
2 5 5
3 4 5
4 2 2
4 5 5
6 4 5

 

출력 예제

2 : 11
3 : 4
4 : 9
5 : 14
6 : impossible

 

코드

package com.example.codingtest;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

// 각 간선을 나타내는 클래스 Edge
class Edge {
    public int vex, cost; // vex: 연결된 정점, cost: 해당 정점까지의 비용

    // 생성자: 정점과 비용을 초기화
    public Edge(int vex, int cost) {
        this.vex = vex;
        this.cost = cost;
    }
}

class Main {
    static int n, m;  // 정점의 수와 간선의 수
    static ArrayList<ArrayList<Edge>> graph;  // 그래프의 인접 리스트 표현
    static int[] dis;  // 최단 거리를 저장하는 배열

    // 다익스트라 알고리즘 구현
    public static void solution(int v){
        // 우선순위 큐 사용: 비용이 작은 순으로 처리하기 위해 Comparator 설정
        PriorityQueue<Edge> pQ = new PriorityQueue<>((a, b) -> a.cost - b.cost);
        
        // 시작 정점 v에서 시작, 초기 비용은 0
        pQ.offer(new Edge(v, 0));
        dis[v] = 0;  // 시작 정점까지의 비용은 0

        while (!pQ.isEmpty()) {
            Edge tmp = pQ.poll();  // 가장 작은 비용의 정점을 꺼낸다
            int now = tmp.vex;  // 현재 정점
            int nowCost = tmp.cost;  // 현재 정점까지의 비용

            // 기존 비용보다 더 큰 비용으로 이 정점에 도달했으면 무시
            if (nowCost > dis[now]) {
                continue;
            }

            // 현재 정점에서 연결된 모든 정점을 확인
            for (Edge ob : graph.get(now)) {
                // 새로운 경로를 통해 연결된 정점 ob.vex로 가는 비용이 더 적다면 갱신
                if (dis[ob.vex] > nowCost + ob.cost) {
                    dis[ob.vex] = nowCost + ob.cost;  // 최소 비용 갱신
                    pQ.offer(new Edge(ob.vex, nowCost + ob.cost));  // 새로운 경로 추가
                }
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        // 정점의 수 n과 간선의 수 m 입력받기
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        // 그래프 초기화
        graph = new ArrayList<ArrayList<Edge>>();
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<Edge>());
        }

        // 최단 거리 배열을 무한대로 초기화
        dis = new int[n + 1];
        Arrays.fill(dis, Integer.MAX_VALUE);

        // 간선 정보를 입력받아 그래프에 추가
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());  // 출발 정점
            int b = Integer.parseInt(st.nextToken());  // 도착 정점
            int c = Integer.parseInt(st.nextToken());  // 비용
            graph.get(a).add(new Edge(b, c));  // 그래프에 간선 추가
        }

        // 1번 정점에서 시작하여 다익스트라 알고리즘 수행
        solution(1);

        // 2번 정점부터 n번 정점까지의 최단 거리를 출력
        for (int i = 2; i <= n; i++) {
            if (dis[i] != Integer.MAX_VALUE) {
                System.out.println(i + " : " + dis[i]);  // 경로가 있으면 최소 비용 출력
            } else {
                System.out.println(i + " : impossible");  // 경로가 없으면 "impossible" 출력
            }
        }
    }
}

1. Edge 클래스

• 각 간선의 정보를 저장하기 위한 클래스이다. 간선은 두 가지 정보를 가진다:
  • vex: 연결된 정점.
  • cost: 정점까지의 비용.
• 생성자를 통해 간선 정보를 초기화한다.

2. Main 클래스

• 정점의 수 n, 간선의 수 m을 전역 변수로 선언.
• graph: 그래프를 인접 리스트로 표현하기 위해 ArrayList<ArrayList<Edge>>를 사용하여 각 정점에서 연결된 간선들의 리스트를 관리.
• dis: 출발 정점에서 다른 정점까지의 최단 거리를 저장하는 배열이다. 무한대로 초기화하여 아직 도달하지 않은 정점을 표시한다.

3. solution(int v) 함수

1) 다익스트라 알고리즘

1. 우선순위 큐 사용: 비용이 가장 작은 경로를 우선적으로 처리하기 위해 PriorityQueue를 사용한다.
2. 시작점 설정: 출발 정점 v에서 출발하며, 그 비용은 0이다. 따라서 우선순위 큐에 (v, 0)을 넣는다.
3. 큐에서 정점 꺼내기: 큐에서 가장 작은 비용을 가진 정점을 꺼낸다.
4. 기존 비용과 비교: 기존에 저장된 비용보다 더 큰 비용으로 도달하면 무시한다.
5. 인접 정점 갱신: 현재 정점에서 인접한 정점으로 가는 비용이 더 작으면 그 비용을 갱신하고, 해당 정점을 큐에 넣는다.

4. main 함수

1. 입력 처리: 정점의 수와 간선의 수를 입력받는다.
2. 그래프 초기화: 정점의 수에 맞게 인접 리스트를 초기화한다.
3. 간선 정보 입력: 각 간선의 출발점, 도착점, 비용을 입력받고 그래프에 저장한다.
4. 다익스트라 알고리즘 호출: 출발점은 1번 정점으로 고정하고 다익스트라 알고리즘을 수행한다.
5. 결과 출력: 2번 정점부터 각 정점까지의 최소 비용을 출력하고, 경로가 없으면 impossible을 출력한다.

다익스트라 알고리즘의 핵심

1. 최소 비용 경로를 우선적으로 계산하여 다른 경로보다 빠르게 도달할 수 있는지 확인한다.
2. 우선순위 큐를 사용하여 가장 적은 비용의 경로부터 탐색하기 때문에 효율적이다.
3. 시간 복잡도는 O(E log V)로, 간선의 수와 정점의 수에 비례하여 성능이 결정된다.