图论没学还是最大的问题 打个笔记自用 没干货
先记迪杰斯特拉 floyd后面再整

原题链接
单源带权图 求“源点到其它节点的最短路径”的最大值

建图
times[i] = (ui, vi, wi)，其中 ui 是源节点，vi 是目标节点， wi 是一个信号从源节点传递到目标节点的时间

邻接矩阵

int[][] g = new int[n + 1][n + 1];
for (int i = 1; i <= n; i++) Arrays.fill(g[i], Integer.MAX_VALUE);  // 不可达记为距离无限大
for (int[] i : times) g[i[0]][i[1]] = i[2];

邻接表

ArrayList<int[]>[] u = new ArrayList[n + 1];
for (int i = 1; i <= n; i++) u[i] = new ArrayList<>();
for (int[] i : times) u[i[0]].add(new int[] {i[1], i[2]});

DFS Or BFS

但是因为带权 随着距离变化 搜过的节点可能多次被搜到 效果不理想 $350 ms$

开一个数组dist[] 记录源点k到其他节点的距离 初始化为无限大 且dist[k] = 0
从源点开始搜索 遍历所有邻居 将距离置为dist[cur] + g[cur][next] 并以当前邻居为起点进行下一轮搜索
注意当新的距离dist[cur] + g[cur][next] 大于 邻居已记录的距离dist[next]时 可以直接跳过 不必再搜

邻接表+DFS

class Solution {
    ArrayList<int[]>[] u;  // 邻接表
    int[] dist;  // 记录距离

    void dfs(int idx) {
        for (int[] next : u[idx]) {
            if (dist[idx] + next[1] >= dist[next[0]]) continue;  // 如果距离大于记录值 则略过
            dist[next[0]] = dist[idx] + next[1];  // 否则更新源点到邻居的距离
            dfs(next[0]);  // 从邻居节点开始搜下一层
        }
    }

    public int networkDelayTime(int[][] times, int n, int k) {
        u = new ArrayList[n + 1];
        for (int i = 1; i <= n; i++) u[i] = new ArrayList<>(); 

        dist = new int[n + 1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[k] = 0;

        for (int[] i : times) u[i[0]].add(new int[] {i[1], i[2]});  // 邻接表建图

        dfs(k);
        int ans = 0;
        for (int i = 1; i <= n; i++)  // 遍历最后的距离数组 找最大值
            if (dist[i] > ans) ans = dist[i];
        return ans == Integer.MAX_VALUE ? -1 : ans;  // 如果最大值是MAX_VALUE 说明有节点不可达 返回-1
    }
}

$O(n^2)$迪杰斯特拉

朴素版本 原理不多说 就是每次从当前未确定的节点里找“离源点最近的点” 然后标记该点已确定 并更新所有可达点的最短距离

主要模板怎么打

建图 这里用邻接矩阵 表也行
距离数组dist[] 同样初始化为无限大 dist[k] = 0
布尔数组vis[] 标记某节点是否已确定

while(true)开始搜 直到所有点都被确定 break
每次循环 先一次遍历dist[]找未确定且距离最小的节点编号idx
标记节点已确定 vis[idx] = true
搜节点的所有邻居 当“经由本点idx到邻居i的路径距离更短”时 即dist[idx] + g[idx][i] < dist[i] 更新dist[i]

class Solution {
    public int networkDelayTime(int[][] times, int n, int k) {
        int[][] g = new int[n + 1][n + 1];  // 邻接矩阵建图
        for (int i = 1; i <= n; i++) Arrays.fill(g[i], Integer.MAX_VALUE);
        for (int[] i : times) g[i[0]][i[1]] = i[2];

        boolean[] vis = new boolean[n + 1];  // 标记节点是否确定
        int[] dist = new int[n + 1];  // 记录节点到源点的距离
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[k] = 0;  // 初始时源点到源点的距离为0

        while (true) {
            int idx = 0, minv = Integer.MAX_VALUE;  // 节点编号从1到n 0是无用编号
            for (int i = 1; i <= n; i++) 
                if (!vis[i] && dist[i] < minv) {  // 找未确定且dist[]最小的节点编号
                    idx = i;
                    minv = dist[i];
                }

            if (idx == 0) break;  // 如果最终节点编号为0 说明所有节点都被确定了 退出循环 
            else vis[idx] = true;  // 否则标记该节点为已确定

            for (int i = 1; i <= n; i++) {  // 搜节点邻居
                if (minv < dist[i] - g[idx][i])  // 更新条件为 (dist[idx] + g[idx][i] < dist[i]) 防溢出 变形为减法
                    dist[i] = minv + g[idx][i];
            }
        }

        int ans = 0;
        for (int i = 1; i <= n; i++)  // 遍历最后的距离数组 找答案 
            if (dist[i] > ans) ans = dist[i];
        return ans == Integer.MAX_VALUE ? -1 : ans;
    }
}

$O(nlogn)$迪杰斯特拉 堆优化

每次都要遍历dist[]找最小的 然后再放入新的距离到其他位置
考虑用小根堆存当前已经找到的所有未确定节点的距离 存取都是$O(logn)$的开销
（但是dist[]需要保留）
每次循环取出队首节点 如果节点未被确定（dist[idx]值为无限大） 就更新dist[idx] 如果已确定则跳过（上次被 确定的必然距离更小）
然后遍历所有邻居 对未确定的邻居节点 算出距离 并放入小根堆
直到循环队列被取空 循环结束

邻接表+堆优化

class Solution {
    public int networkDelayTime(int[][] times, int n, int k) {
        ArrayList<int[]>[] u = new ArrayList[n + 1];  // 邻接表建图
        for (int i = 1; i <= n; i++) u[i] = new ArrayList<>();
        for (int[] i : times) u[i[0]].add(new int[] {i[1], i[2]});

        PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> o1[1] - o2[1]);  // 小根堆
        pq.add(new int[] {k, 0});  // 源点入队

        int[] dist = new int[n + 1];
        Arrays.fill(dist, Integer.MAX_VALUE);

        while (!pq.isEmpty()) {
            int[] cur = pq.poll();  // 找当前距离最小的点
            if (cur[1] >= dist[cur[0]]) continue;  // 如果大于已记录的距离 就跳过
            else dist[cur[0]] = cur[1];  // 否则确定节点 并更新距离
            for (int[] next : u[cur[0]]) {  // 遍历邻居节点
                int d = next[1] + cur[1];  // 新的距离
                if (d >= dist[next[0]]) continue;  // 距离大于已记录的就跳过
                pq.add(new int[] {next[0], d});  // 否则入队
            }
        }

        int ans = 0;
        for (int i = 1; i <= n; i++) 
            if (dist[i] == Integer.MAX_VALUE) return -1;
            else if (dist[i] > ans) ans = dist[i];
        return ans;
    }
}