--- title: "다익스트라: 비음수 edge에서 거리 확정을 증명하는 Java 최단 경로" slug: "java-dijkstra" category: "CS" topic: "cs" subtopic: "algorithms" tags: ["Java","Dijkstra","Shortest Path","PriorityQueue","Graph"] status: "published" created: "2026-08-06" updated: "2026-08-06" summary: "relaxation·최소 우선순위·stale entry가 만드는 거리 불변식을 증명하고, 음수 반례·long overflow·객체 allocation·대안 선택까지 추적한다." kind: "Deep Dive" evidence: "Dijkstra 1959 원 논문·Princeton Algorithms 4/e shortest paths·Java SE 21 PriorityQueue API를 대조하고 DijkstraDemo를 OpenJDK 21.0.11에서 실행" series: "Java Essential Algorithms" --- 다익스트라는 source에서 각 정점까지 **비음수 edge weight 합**의 최솟값을 구한다. priority queue에서 현재 tentative distance가 가장 작은 정점을 꺼내 outgoing edge를 relaxation한다. 음수 edge가 하나라도 있으면 이미 확정했다고 믿은 거리가 나중에 더 작아질 수 있어 핵심 증명이 깨진다. ## 1. 문제 계약과 결과 정점 `0..V-1`, directed `Edge(to,weight)` adjacency와 source를 받는다. weight는 0 이상 long이다. 결과 distance는 도달 불가능하면 `Long.MAX_VALUE`, parent로 실제 경로를 복원한다. 범위 밖 edge와 음수 weight는 예외다. distance와 weight를 int로 두면 긴 경로 합이 wraparound해 더 짧은 음수처럼 보일 수 있다. long도 overflow할 수 있으므로 `current > Long.MAX_VALUE-weight`이면 그 후보 덧셈을 건너뛴다. 도메인에서 그 경로를 오류로 보아야 한다면 예외 정책으로 바꾼다. ## 2. relaxation 상태 추적 edge `0->1(4), 0->2(1), 2->1(2), 1->3(1)` 일부를 본다. | poll | 현재 거리 | relaxation | distance 변화 | PQ | | ---: | ---: | --- | --- | --- | | 0 | 0 | 0→1, 0→2 | `d1=4,d2=1` | `(2,1),(1,4)` | | 2 | 1 | 2→1 | `d1:4→3` | `(1,3),(1,4)` | | 1 | 3 | 1→3 | `d3=4` | `(1,4 stale),(3,4)` | | 1 | 4 | stale 검사 | 무시 | `(3,4)` | Java PriorityQueue에는 decrease-key API가 없다. 더 짧은 candidate를 새 Node로 넣고, 꺼낼 때 현재 `distance[vertex]`와 다르면 stale entry로 버린다. ## 3. 불변식과 거리 확정 증명 **불변식 1:** `distance[v]`는 지금까지 발견한 source→v 경로 중 최소 길이다. relaxation이 실제 edge를 붙인 경로만 기록하므로 항상 유효한 경로 길이다. **불변식 2:** non-stale 최소 Node `(u,d)`를 꺼낼 때 d보다 짧은 미발견 source→u 경로는 없다. 있다고 가정하고 그 경로에서 확정 집합을 처음 벗어나는 edge `x->y`를 잡자. x까지는 이미 처리됐고 weight가 비음수이므로 y의 candidate는 전체 경로 길이 이하로 PQ에 들어갔어야 한다. 그런데 u가 최소로 먼저 나왔다는 사실과 모순이다. 따라서 non-stale poll의 거리는 확정 가능하다. 음수 edge가 있으면 x 이후의 suffix가 거리를 낮출 수 있어 이 부등식이 성립하지 않는다. ## 실행 재현 아래 코드는 설명용 조각이 아니라 `main`에 정상·빈 입력·중복·경계·실패 계약을 함께 넣은 완전한 Java 21 프로그램이다. ```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 { public int compareTo(Node other) { return Long.compare(distance, other.distance); } } record Result(long[] distance, int[] parent) { List pathTo(int target) { if (target < 0 || target >= distance.length) throw new IllegalArgumentException("invalid target"); if (distance[target] == Long.MAX_VALUE) return List.of(); List 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> 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 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> graph(int vertices, long[][] edges) { List> 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> 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"); } } ``` ```bash javac --release 21 DijkstraDemo.java java DijkstraDemo ``` 직접 실행한 출력은 다음과 같다. ```text distance(4)=7, path=[0, 2, 1, 3, 4], negative=rejected ``` 컴파일러와 런타임은 `javac 21.0.11`, OpenJDK `21.0.11`을 사용했다. `assert` 옵션에 의존하지 않고 실패 시 `AssertionError`를 던지므로 위 명령 그대로 검증된다. ## 4. 음수 반례 `0->A(2), 0->B(5), B->A(-10)`에서 A=2를 먼저 확정하면 나중 경로 `0->B->A=-5`가 더 짧다. 예제는 음수 edge를 발견 즉시 거절한다. 음수 edge가 있고 음수 cycle이 없을 때는 Bellman-Ford, DAG라면 위상 순서 relaxation을 검토한다. ## 5. 시간·공간 복잡도 binary heap PriorityQueue에서 offer/poll은 API 구현 note상 $O(\log n)$이다. decrease-key 대신 edge relaxation 성공마다 새 entry를 넣으므로 PQ entry가 $O(E)$까지 생길 수 있다. 각 edge를 한 번 검사하고 각 성공 offer/poll이 로그 비용을 가져 거친 bound는 $O((V+E)\log E)$, 흔히 $O((V+E)\log V)$ 계열로 표기할 때는 heap 크기/구현 가정을 밝혀야 한다. distance와 parent는 $O(V)$, adjacency는 입력 $O(V+E)$, PQ는 stale entry 포함 최악 $O(E)$다. “Dijkstra 보조 공간 $O(V)$”라고 단정하면 이 Java 구현과 맞지 않는다. ## 6. JVM allocation과 comparator 각 `new Node(vertex,candidate)` record는 heap allocation 후보이고 PriorityQueue backing reference array도 heap에 있다. stale 전략은 구현을 단순화하지만 successful relaxation 수만큼 임시 Node를 만들어 allocation/GC pressure가 될 수 있다. escape analysis로 실제 할당이 제거될지는 JVM 최적화 결과이지 Java 계약이 아니다. JFR allocation event로 확인한다. `compareTo`는 `Long.compare`를 사용한다. `(int)(distance-other.distance)` 같은 뺄셈 comparator는 overflow와 comparator 계약 위반을 일으킬 수 있다. ## 7. BFS·Bellman-Ford·A*와 비교 | 입력/목표 | 선택 | 핵심 조건 | | --- | --- | --- | | 모든 weight 동일 | BFS | FIFO layer가 더 단순 | | 비음수 weight | Dijkstra | 최소 tentative 확정 | | 음수 edge, 음수 cycle 검출 | Bellman-Ford | 반복 relaxation | | 단일 target + admissible heuristic | A* | heuristic 품질/정당성 | | DAG weight | topological relaxation | cycle 없음 | A*는 “더 빠른 Dijkstra”가 자동으로 아니다. heuristic이 admissible/consistent해야 최적성 계약을 지키며 도메인별 설계가 필요하다. ## 8. 실제 도메인 적용 network routing 비용, road travel time snapshot, service dependency의 누적 latency 후보에 쓸 수 있다. weight가 request 중 바뀌면 계산 snapshot 일관성이 깨진다. 관측 지표는 visited vertices, relaxations, stale poll ratio, max PQ size, query timeout, graph version이다. 음수 rebate/credit가 있는 가격 graph에는 그대로 쓰지 않는다. ## 9. 이건 피한다 - **음수 edge를 허용한다.** 거리 확정 증명이 깨져 오답이 된다. 입력 검증 후 Bellman-Ford/DAG 알고리즘을 선택한다. - **distance를 int로 둔다.** 합 overflow가 더 짧은 경로처럼 보인다. long과 덧셈 overflow guard를 쓴다. - **stale entry를 처리하면서도 무조건 edge를 다시 훑는다.** CPU와 allocation이 증가한다. 현재 distance와 다르면 즉시 continue한다. - **PriorityQueue iterator가 정렬됐다고 믿는다.** API는 iterator 순서를 보장하지 않는다. 순차 최소 추출은 poll을 사용한다. - **동적 weight를 한 snapshot처럼 계산한다.** 경로가 어느 시점에도 존재하지 않는 조합이 될 수 있다. graph version/snapshot을 고정한다. ## Reference - E. W. Dijkstra, [A note on two problems in connexion with graphs, Numerische Mathematik 1, 1959](https://doi.org/10.1007/BF01386390) - Robert Sedgewick, Kevin Wayne, [Algorithms, 4th Edition — Shortest Paths](https://algs4.cs.princeton.edu/44sp/) - Oracle, [PriorityQueue — Java SE 21 API](https://docs.oracle.com/en/java/javase/21/docs/api/java.base/java/util/PriorityQueue.html) - Oracle, [The Java Language Specification, Java SE 21 — Integer Operations](https://docs.oracle.com/javase/specs/jls/se21/html/jls-4.html#jls-4.2.2) - Oracle, [The Java Virtual Machine Specification, Java SE 21 — Heap and Frames](https://docs.oracle.com/javase/specs/jvms/se21/html/jvms-2.html#jvms-2.5)