Dijkstra 算法概述
Dijkstra 算法的核心思想是一种贪心策略。它从一个起始节点开始，逐步向外扩展，每次都选择离起点最近且未被访问过的节点，并用该节点来更新其所有邻居节点到起点的最短距离。

这个过程可以形象地理解为，从起点向四周铺设一条条路径，每次都优先铺设最短的那条，直到所有可达的节点都被铺设完毕。

算法步骤
1.dist[i]表示从源点到i的最短距离，visited[i]表示i节点是否从小根堆弹出过
2.准备好小根堆，小根堆存放记录：(x点，x到源点距离)，小根堆根据距离组织
3.令dist[源点]=0，(源点，0)进入小根堆
4.从小根堆弹出(u,源点到u的距离)
a.如果visited[u]==true ,不做任何处理，重复步骤4
b.如果visited[u]==false,令为true，u也算弹出过了
然后考察u的每一条边，假设某边去v，边权w
1)如果visited[v]==false 并且dist[u]+w <dist[v]
令dist[v] = dist[u]+w 把(v,dist[u]+w)加入小根堆
2)处理完u的每一条边，重复4
5.小根堆为空过程结束，dist表记录了源点到节点的最短距离

为什么 Dijkstra 算法不能处理负权边？
Dijkstra 算法的贪心策略依赖于边权非负的特性。在每次选择时，它总是认为当前距离最短的节点就是其最终的最短路径。如果存在负权边，这个假设就不成立了。

举个例子，假设我们有一个节点 A，它到 B 的距离是 5。但存在一条负权边从 C 到 D，使得通过某条路径从 A 到 C，再经过负权边到达 D，最后到 B 的距离变得比 5 更小。如果 Dijkstra 算法先选择了 B，它就会错过这条更短的路径。

因此，对于包含负权边的图，需要使用其他算法，如Bellman-Ford或SPFA。

给定一个源点，求解从源点到每个点的最短路径长度。单源最短路径算法。
适用于：有向图，边权值不为负数
最核心的：
节点弹出过就忽略
节点没弹出过，让其他没弹出节点距离变小的记录加入堆。

package class064;

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

// Dijkstra算法模版（Leetcode）
// 网络延迟时间
// 有 n 个网络节点，标记为 1 到 n
// 给你一个列表 times，表示信号经过 有向 边的传递时间
// times[i] = (ui, vi, wi)，表示从ui到vi传递信号的时间是wi
// 现在，从某个节点 s 发出一个信号
// 需要多久才能使所有节点都收到信号
// 如果不能使所有节点收到信号，返回 -1
// 测试链接 : https://leetcode.cn/problems/network-delay-time
pclass Solution {

// Dijkstra算法模版（Leetcode）
// 网络延迟时间
// 有 n 个网络节点，标记为 1 到 n
// 给你一个列表 times，表示信号经过 有向 边的传递时间
// times[i] = (ui, vi, wi)，表示从ui到vi传递信号的时间是wi
// 现在，从某个节点 s 发出一个信号
// 需要多久才能使所有节点都收到信号
// 如果不能使所有节点收到信号，返回 -1

    // 动态建图+普通堆的实现
    public static int networkDelayTime(int[][] times, int n, int s) {
        ArrayList<ArrayList<int[]>> graph = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }
        for (int[] edge : times) {
            graph.get(edge[0]).add(new int[] { edge[1], edge[2] });
        }
        int[] distance = new int[n + 1];
        Arrays.fill(distance, Integer.MAX_VALUE);
        distance[s] = 0;
        boolean[] visited = new boolean[n + 1];
        // 0 : 当前节点
        // 1 : 源点到当前点距离
        PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> a[1] - b[1]);
        heap.add(new int[] { s, 0 });
        while (!heap.isEmpty()) {
            int u = heap.poll()[0];
            if (visited[u]) {
                continue;
            }
            visited[u] = true;
            for (int[] edge : graph.get(u)) {
                int v = edge[0];
                int w = edge[1];
                if (!visited[v] && distance[u] + w < distance[v]) {
                    distance[v] = distance[u] + w;
                    heap.add(new int[] { v, distance[u] + w });
                }
            }
        }
        int ans = Integer.MIN_VALUE;
        for (int i = 1; i <= n; i++) {
            if (distance[i] == Integer.MAX_VALUE) {
                return -1;
            }
            ans = Math.max(ans, distance[i]);
        }
        return ans;
    }
    }