다익스트라

/* ── 매 단계 미확정 노드 중 거리가 가장 짧은 노드를 선택 ───── */
public int[] dijkstra(int src, int[][] adjMatrix) {
    int n = adjMatrix.length;
    int[] dist = new int[n];
    boolean[] visited = new boolean[n];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[src] = 0;

    for (int count = 0; count < n; count++) {
        int u = -1;
        for (int i = 0; i < n; i++) {          // 미확정 노드 중 최솟값 탐색 — O(V)
            if (!visited[i] && (u == -1 || dist[i] < dist[u])) u = i;
        }
        if (dist[u] == Integer.MAX_VALUE) break;  // 남은 노드가 모두 도달 불가능
        visited[u] = true;

        for (int v = 0; v < n; v++) {              // u의 모든 인접 노드 완화(relax)
            if (adjMatrix[u][v] > 0 && !visited[v] && dist[u] + adjMatrix[u][v] < dist[v]) {
                dist[v] = dist[u] + adjMatrix[u][v];
            }
        }
    }
    return dist;
}

/* ── 최소 힙으로 "다음 확정 후보"를 빠르게 꺼냄 ───────────── */
public int[] dijkstraPQ(int src, List<List<int[]>> adj, int n) {
    int[] dist = new int[n];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[src] = 0;

    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);  // [노드, 거리] 오름차순
    pq.offer(new int[]{src, 0});

    while (!pq.isEmpty()) {
        int[] cur = pq.poll();
        int u = cur[0], d = cur[1];
        if (d > dist[u]) continue;         // 이미 더 짧은 경로로 확정된 노드 — 오래된 항목 무시

        for (int[] edge : adj.get(u)) {
            int v = edge[0], w = edge[1];
            if (d + w < dist[v]) {
                dist[v] = d + w;
                pq.offer(new int[]{v, dist[v]});   // 갱신된 거리로 큐에 다시 추가
            }
        }
    }
    return dist;
}

/* ── 완화 성공 시 prev[v]=u를 기록해두면 경로 복원 가능 ────── */
if (dist[u] + w < dist[v]) {
    dist[v] = dist[u] + w;
    prev[v] = u;                       // "v는 u를 거쳐서 왔다"를 기록
}

/* ── 목표 노드에서 시작 노드 방향으로 거슬러 올라가며 경로 복원 ── */
public List<Integer> reconstructPath(int target, int[] prev) {
    List<Integer> path = new LinkedList<>();
    for (int at = target; at != -1; at = prev[at]) {
        path.add(0, at);              // 맨 앞에 삽입 → 최종적으로 시작→목표 순서가 됨
    }
    return path;
}