迪杰斯特拉（Dijkstra）算法模板

import java.util.*;

/**
 * 迪杰斯特拉算法标准模板
 */
public class Dijkstra {
    static int N, A, B; // 点个数，起始位置，结束位置
    static Map<Integer, Set<Integer>> LINKS; // 链接点的路径

    static int[] DIS; // 每个点到起始位置的距离
    static boolean[] VISITED; // 点是否访问的标记（没有这个不影响结果，有这个是因为时间性能上的优化）

    public static void main(String[] args) {
        LINKS = new HashMap<>(); // 路径初始化忽略
        DIS = new int[N + 1]; // A，B从1开始计数
        Arrays.fill(DIS, Integer.MAX_VALUE);
        VISITED = new boolean[N + 1];
        dijkstra();
        // -1表示不可达
        System.out.println(DIS[B] == Integer.MAX_VALUE ? -1 : DIS[B]);
    }

    /**
     * 迪杰斯特拉算法实现
     */
    private static void dijkstra() {
        // 使用优先队列（可根据实际情况调整排序算法，此处最小优先）
        Queue<Integer> queue = new PriorityQueue<>(Comparator.comparing(x -> DIS[x]));
        // 设置起始位置状态
        queue.offer(A);
        DIS[A] = 0;
        VISITED[A] = true;

        while (!queue.isEmpty()) {
            Integer curr = queue.poll();

            if (curr == B) {
                return; // 结束位置达到，退出
            }

            if (!LINKS.containsKey(curr)) {
                continue; // 无后续的路径可走
            }

            for (Integer next : LINKS.get(curr)) {
                if (!VISITED[next] && DIS[curr] + 1 < DIS[next]) {
                    // 没有访问的点，并且路径此时最小，则更新距离和访问标记
                    DIS[next] = DIS[curr] + 1;
                    VISITED[next] = true;
                    // 新的下一个点加入队列
                    queue.offer(next);
                }
            }
        }
    }
}