다익스트라: 비음수 edge에서 거리 확정을 증명하는 Java 최단 경로

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.PriorityQueue;

public final class DijkstraDemo {
    record Edge(int to, long weight) {}
    record Node(int vertex, long distance) implements Comparable<Node> {
        public int compareTo(Node other) { return Long.compare(distance, other.distance); }
    }
    record Result(long[] distance, int[] parent) {
        List<Integer> pathTo(int target) {
            if (target < 0 || target >= distance.length) throw new IllegalArgumentException("invalid target");
            if (distance[target] == Long.MAX_VALUE) return List.of();
            List<Integer> reversed = new ArrayList<>();
            for (int at = target; at != -1; at = parent[at]) reversed.add(at);
            Collections.reverse(reversed);
            return List.copyOf(reversed);
        }
    }

    static Result shortestPaths(List<List<Edge>> graph, int source) {
        if (graph == null || source < 0 || source >= graph.size()) throw new IllegalArgumentException("invalid graph/source");
        long[] distance = new long[graph.size()];
        int[] parent = new int[graph.size()];
        Arrays.fill(distance, Long.MAX_VALUE);
        Arrays.fill(parent, -1);
        PriorityQueue<Node> pq = new PriorityQueue<>();
        distance[source] = 0;
        pq.offer(new Node(source, 0));
        while (!pq.isEmpty()) {
            Node current = pq.poll();
            if (current.distance() != distance[current.vertex()]) continue;
            for (Edge edge : graph.get(current.vertex())) {
                if (edge.to() < 0 || edge.to() >= graph.size()) throw new IllegalArgumentException("invalid edge");
                if (edge.weight() < 0) throw new IllegalArgumentException("negative edge");
                if (current.distance() > Long.MAX_VALUE - edge.weight()) continue;
                long candidate = current.distance() + edge.weight();
                if (candidate < distance[edge.to()]) {
                    distance[edge.to()] = candidate;
                    parent[edge.to()] = current.vertex();
                    pq.offer(new Node(edge.to(), candidate));
                }
            }
        }
        return new Result(distance, parent);
    }

    static List<List<Edge>> graph(int vertices, long[][] edges) {
        List<List<Edge>> graph = new ArrayList<>();
        for (int i = 0; i < vertices; i++) graph.add(new ArrayList<>());
        for (long[] edge : edges) graph.get((int) edge[0]).add(new Edge((int) edge[1], edge[2]));
        return graph;
    }

    static void check(boolean condition, String message) {
        if (!condition) throw new AssertionError(message);
    }

    public static void main(String[] args) {
        List<List<Edge>> graph = graph(6, new long[][] {{0,1,4},{0,2,1},{2,1,2},{1,3,1},{2,3,5},{3,4,3}});
        Result result = shortestPaths(graph, 0);
        check(result.distance()[4] == 7, "distance");
        check(result.pathTo(4).equals(List.of(0, 2, 1, 3, 4)), "path");
        check(result.distance()[5] == Long.MAX_VALUE, "unreachable");
        try {
            shortestPaths(graph(2, new long[][] {{0,1,-1}}), 0);
            throw new AssertionError("negative edge expected");
        } catch (IllegalArgumentException expected) {
            check(expected.getMessage().equals("negative edge"), "negative reason");
        }
        System.out.println("distance(4)=7, path=" + result.pathTo(4) + ", negative=rejected");
    }
}

javac --release 21 DijkstraDemo.java
java DijkstraDemo

distance(4)=7, path=[0, 2, 1, 3, 4], negative=rejected