다익스트라 알고리즘 feat:BOJ1753 최단경로 JAVA

다익스트라 알고리즘이란?

• 매번 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택하여 한 단계씩 최단 거리를 구해나간다.
• 음수 간선이 없다면 최적의 해를 찾을 수 있다.
• 시간 복잡도가 빠르다 . 개선된 다익스트라 알고리즘도 존재하는데 이는 우선순위 큐 사용해서 구현할 수 있다

 

 

BOJ1753 - 최단경로

https://www.acmicpc.net/problem/1753

 

이 문제는 개선된 다익스트라 형태인 우선순위큐를 활용해서 풀어야 한다

 

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

class Main {
    // 간선 정보를 저장하는 Edge 클래스, 우선순위 큐에서 비교를 위해 Comparable 인터페이스 구현
    public static class Edge implements Comparable<Edge> {
        int end;  // 도착 노드
        int cost; // 간선의 비용

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

        @Override
        public int compareTo(Edge edge) {
            return cost - edge.cost; // 비용을 기준으로 오름차순 정렬
        }
    }

    // 노드들의 인접 리스트 배열
    public static List<Edge>[] nodes;
    // 최단 거리 저장 배열
    public static int[] dist;
    // 노드의 개수, 간선의 개수, 시작 노드
    public static int N, M, start;
    // 무한대 값을 상수로 정의
    private static final int INF = 100_000_000;

    public static void main(String[] args) throws IOException {
        // 입력을 받기 위한 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken()); // 노드의 수
        M = Integer.parseInt(st.nextToken()); // 간선의 수

        start = Integer.parseInt(br.readLine()); // 시작 노드

        // 최단 거리 배열 초기화
        dist = new int[N + 1];
        Arrays.fill(dist, INF);

        // 노드들의 인접 리스트 배열 초기화
        nodes = new ArrayList[N + 1];
        for (int i = 1; i <= N; i++) {
            nodes[i] = new ArrayList<>();
        }

        // 간선 정보 입력
        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()); // 비용

            nodes[a].add(new Edge(b, c)); // 간선 리스트에 추가
        }

        // 다익스트라 알고리즘 수행
        dijkstra(start);

        // 결과 출력
        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= N; i++) {
            if (dist[i] == INF) {
                sb.append("INF\n"); // 도달할 수 없는 경우 INF 출력
            } else {
                sb.append(dist[i]).append("\n"); // 최단 거리 출력
            }
        }
        System.out.println(sb.toString());
    }

    // 다익스트라 알고리즘 메서드
    public static void dijkstra(int start) {
        PriorityQueue<Edge> pq = new PriorityQueue<>();
        // 우선순위 큐에 시작 노드 추가
        pq.add(new Edge(start, 0));
        dist[start] = 0;

        // 다익스트라 알고리즘 수행
        while (!pq.isEmpty()) {
            Edge node = pq.poll(); // 최소 비용의 노드 선택
            int cur = node.end;

            // 이미 처리된 노드는 무시
            if (node.cost > dist[cur]) continue;

            // 현재 노드와 연결된 인접 노드들에 대해 최단 거리 갱신
            for (Edge e : nodes[cur]) {
                if (dist[e.end] > dist[cur] + e.cost) {
                    dist[e.end] = dist[cur] + e.cost; // 최단 거리 갱신
                    pq.add(new Edge(e.end, dist[e.end])); // 갱신된 노드 큐에 추가
                }
            }
        }
    }
}