算法

Dijstra算法

求单源最短路径

class Solution {
    int[][] w = new int[N][N];
    int[] dist = new int[N];
    boolean[] vis = new boolean[N];
    int INF = 0x3f3f3f3f; // MAX_VALUE
    public int networkDelayTime(int[][] ts, int n, int k) {
        //邻接矩阵初始化 
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                w[j][i] = i == j ? 0 : INF;
                w[i][j] = w[j][i];
            }
        }
        // 更新临接矩阵
        for (int[] t : ts) {
            int u = t[0];
            int v = t[1];
            int c = t[2];
            w[u][v] = c;
        }
        // 求最短路
        // 起始先将所有的点标记为「未更新」和「距离为正无穷」
        Arrays.fill(vis, false);
        Arrays.fill(dist, INF);
        dijkstra();
    }
    void dijkstra() {
        dist[k] = 0;
        // 迭代 n 次
        for (int p = 1; p <= n; p++) {
            //找到新的最近的点t
            int t = -1;
            for (int i = 1; i <= n; i++) {
                if (!vis[i] && (t == -1 || dist[i] < dist[t])) t = i;
            }
            vis[t] = true;
            //更新最短距离
            for (int i = 1; i <= n; i++) {
                dist[i] = Math.min(dist[i], dist[t] + w[t][i]);
            }
        }
    }

拓扑排序

判断DAG 有向无环图

• 建立入度表
• 建立邻接表
• 建立队列
  • 入度为0的点加入队列
• 开始出队
  • 将对应入度减一
  • 入度为0的点入队

• 出队时记录一下

  class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        int[] in = new int[numCourses];
        List<List<Integer>> adj = new ArrayList();
        Queue<Integer> queue = new LinkedList();
        for(int i = 0; i < numCourses; i++){
            adj.add(new ArrayList());
        }
        for(int[] cp : prerequisites) {
            in[cp[0]] = in[cp[0]] + 1;
            adj.get(cp[1]).add(cp[0]);
        }
        for(int i = 0; i < numCourses; i++){
            if(in[i] == 0) queue.add(i);
        }
        while(!queue.isEmpty()) {
            int pre = queue.poll();
            numCourses--;
            for(int cur : adj.get(pre)) {
               if(--in[cur] == 0) queue.add(cur);
            }
        }
        return numCourses == 0;
    }
  }

  例

  网络延迟时间

  ```java 有 n 个网络节点，标记为 1 到 n。 给你一个列表 times，表示信号经过 有向 边的传递时间。 times[i] = (ui, vi, wi)， 其中 ui 是源节点，vi 是目标节点， wi 是一个信号从源节点传递到目标节点的时间。 现在，从某个节点 K 发出一个信号。需要多久才能使所有节点都收到信号？ 如果不能使所有节点收到信号，返回 -1 。

输入：times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2 输出：2

```java
class Solution {
    int N = 110, M = 6010;
    // 邻接矩阵数组：w[a][b] = c 代表从 a 到 b 有权重为 c 的边
    int[][] w = new int[N][N];
    // dist[x] = y 代表从「源点/起点」到 x 的最短距离为 y
    int[] dist = new int[N];
    // 记录哪些点已经被更新过
    boolean[] vis = new boolean[N];
    int INF = 0x3f3f3f3f;
    int n, k;
    public int networkDelayTime(int[][] ts, int _n, int _k) {
        n = _n; k = _k;
        // 初始化邻接矩阵
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                w[i][j] = w[j][i] = i == j ? 0 : INF;
            }
        }
        // 存图
        for (int[] t : ts) {
            int u = t[0], v = t[1], c = t[2];
            w[u][v] = c;
        }
        // 最短路
        dijkstra();
        // 遍历答案
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            ans = Math.max(ans, dist[i]);
        }
        return ans > INF / 2 ? -1 : ans;
    }
    void dijkstra() {
        // 起始先将所有的点标记为「未更新」和「距离为正无穷」
        Arrays.fill(vis, false);
        Arrays.fill(dist, INF);
        // 只有起点最短距离为 0
        dist[k] = 0;
        // 迭代 n 次
        for (int p = 1; p <= n; p++) {
            // 每次找到「最短距离最小」且「未被更新」的点 t
            int t = -1;
            for (int i = 1; i <= n; i++) {
                if (!vis[i] && (t == -1 || dist[i] < dist[t])) t = i;
            }
            // 标记点 t 为已更新
            vis[t] = true;
            // 用点 t 的「最小距离」更新其他点
            for (int i = 1; i <= n; i++) {
                dist[i] = Math.min(dist[i], dist[t] + w[t][i]);
            }
        }
    }
}

所有可能的路径

给你一个有 n 个节点的 有向无环图（DAG），
请你找出所有从节点 0 到节点 n-1 的路径并输出（不要求按特定顺序）
graph[i] 是一个从节点 i 可以访问的所有节点的列表
即从节点 i 到节点 graph[i][j]存在一条有向边）。

输入：graph = [[1,2],[3],[3],[]]
输出：[[0,1,3],[0,2,3]]
解释：有两条路径 0 -> 1 -> 3 和 0 -> 2 -> 3

class Solution {
    List<List<Integer>> res = new ArrayList();
    List<Integer> t = new ArrayList();
    int n;
    int[][] graph;
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        //回溯
        this.n = graph.length;
        this.graph = graph;
        t.add(0);
        bfs(0);
        return res;
    }

    public void bfs(int x){
        if(x == n-1) {
            res.add(new ArrayList(t));
            return;
        }
        for(int y : graph[x]) {
            t.add(y);
            bfs(y);
            t.remove(t.size()-1);
        }
    }
}

课程表

输入：numCourses = 2, prerequisites = [[1,0]]
输出：true
解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是可能的。

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        int[] in = new int[numCourses];
        List<List<Integer>> adj = new ArrayList();
        Queue<Integer> queue = new LinkedList();
        for(int i = 0; i < numCourses; i++){
            adj.add(new ArrayList());
        }
        for(int[] cp : prerequisites) {
            in[cp[0]] = in[cp[0]] + 1;
            adj.get(cp[1]).add(cp[0]);
        }
        for(int i = 0; i < numCourses; i++){
            if(in[i] == 0) queue.add(i);
        }

        while(!queue.isEmpty()) {
            int pre = queue.poll();
            numCourses--;
            for(int cur : adj.get(pre)) {
               if(--in[cur] == 0) queue.add(cur);
            }
        }
        return numCourses == 0;
    }
}