# 算法模板整理

**Repository Path**: code-to-xiaobai/algorithm-template-arrangement

## Basic Information

- **Project Name**: 算法模板整理
- **Description**: 记录自己的刷题之路，将一些类型的题目整理出相关的模板。
- **Primary Language**: Unknown
- **License**: MulanPSL-2.0
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 1
- **Forks**: 0
- **Created**: 2021-07-11
- **Last Updated**: 2022-02-24

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# 算法模板整理

# 最短路径算法


## 单源最短路

- 所有边权都是正数
  - 朴素的Dijkstra算法 O(n^2) 适合稠密图
  - 堆优化版的Dijkstra算法 O(mlog n)（m是图中节点的个数）适合稀疏图
- 存在负权边
  -  Bellman-Ford O(nm)
  -  spfa 一般O(m),最坏O(nm)



当所有边为正的时候，以上几种算法均可使用。这里给出相关的代码模板，具体的理论大家可以自行网上查阅。

贝尔曼-福特算法与[迪科斯彻算法](https://baike.baidu.com/item/迪科斯彻算法)类似，都以松弛操作为基础，即估计的最短路径值渐渐地被更加准确的值替代，直至得到最优解。

## 迪杰斯特拉算法

迪杰斯特拉算法(Dijkstra)是由荷兰计算机[科学家](https://baike.baidu.com/item/科学家/1210114)[狄克斯特拉](https://baike.baidu.com/item/狄克斯特拉/2828872)于1959年提出的，因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的[最短路径](https://baike.baidu.com/item/最短路径/6334920)算法，解决的是有权图中最短路径问题。迪杰斯特拉算法主要特点是从起始点开始，采用[贪心算法](https://baike.baidu.com/item/贪心算法/5411800)的[策略](https://baike.baidu.com/item/策略/4006)，每次遍历到始点距离最近且未访问过的顶点的邻接节点，直到扩展到终点为止。



在[有向图](https://baike.baidu.com/item/有向图) G=(V,E) 中，假设每条边 E[i] 的长度为 w[i]，找到由顶点 V0 到其余各点的最短值。



![输入图片说明](https://images.gitee.com/uploads/images/2021/0712/142328_9c293bca_8927650.png "屏幕截图.png")

**优化后的算法**

```java
public int dijkStra1(int n,int [][]edges,int start,int end){
    //这里的edges = [[begin,end,times],...]这种形式的，也可能是其他形式的，处理方式类似
    Map<Integer, ArrayList<int[]>> graph = new HashMap<>();
    for(int []edge:edges){
        int begin = edge[0];
        int endindex = edge[1];
        int time = edge[2];//这条边的权重
        if(!graph.containsKey(begin))//先判断是否存在begin的集合
            graph.put(begin,new ArrayList<int []>());
        graph.get(begin).add(new int[]{endindex,time});
    }

    //dist数组和visit数组 一个存到当前点的最短路径，一个判断是否访问过
    int []dist = new int[n];//如果从1开始也可以 长度初始化为n+1
    boolean []visit = new  boolean[n];

    //初始化disit数组，根据题目意思初始化 ，如果求最短，则将其初始化为最大；反之一样。
    Arrays.fill(dist,Integer.MAX_VALUE);//默认求最短路径
    dist[start] = 0;//起点一定要记得初始化为0 ！！！

    //new一个小堆出来，按照dis升序排，一定要让它从小到大排，省去了松弛工作
    Queue<Integer> queue = new PriorityQueue<>((o1, o2) -> dist[o1]-dist[o2]);
    //起点入队
    queue.offer(start);
    while (!queue.isEmpty()){
        //获取队头
        int nowindex = queue.poll();//当前队头

        if(visit[nowindex]) continue;
        visit[nowindex] = true;
        //
        ArrayList<int[]> ints = graph.get(nowindex);
        if(ints == null) continue;
        for (int[] anInt : ints) {
            int next = anInt[0];

            if(visit[next]) continue;//已经访问过了
            //这里也有可能是求最长路径，或者是别的变形，就是换一下形式；
            dist[next] =  Math.min(dist[next], dist[nowindex] + anInt[1]);
            queue.offer(next);
        }
    }
    //返回start->end的最短路径， 如果结果为MAX_VALUE，说明无最短，根据题目要求返回要求值
    return dist[end]==Integer.MAX_VALUE?-1:dist[end];
}
```



## 贝尔曼-福特算法

两个算法中，计算时每个边之间的估计距离值都比真实值大，并且被新找到路径的最小长度替代。 然而，迪科斯彻算法以[贪心法](https://baike.baidu.com/item/贪心法)选取未被处理的具有最小权值的节点，然后对其的出边进行松弛操作；而贝尔曼-福特算法简单地对所有边进行松弛操作，共

![输入图片说明](https://images.gitee.com/uploads/images/2021/0712/142344_893f409e_8927650.png "屏幕截图.png")

 次，其中

![输入图片说明](https://images.gitee.com/uploads/images/2021/0712/142351_19348e4c_8927650.png "屏幕截图.png")

 是图的点的数量。在重复地计算中，已计算得到正确的距离的边的数量不断增加，直到所有边都计算得到了正确的路径。这样的策略使得贝尔曼-福特算法比迪科斯彻算法适用于更多种类的输入。



 **松弛**

每次松弛操作实际上是对相邻节点的访问，第

![输入图片说明](https://images.gitee.com/uploads/images/2021/0712/142401_76338350_8927650.png "屏幕截图.png")

次松弛操作保证了所有深度为n的路径最短。由于图的最短路径最长不会经过超过

![输入图片说明](https://images.gitee.com/uploads/images/2021/0712/142407_0d56d628_8927650.png "屏幕截图.png")

条边，所以可知贝尔曼-福特算法所得为最短路径。

 **负边权操作**

与[迪科斯彻算法](https://baike.baidu.com/item/迪科斯彻算法)不同的是，迪科斯彻算法的基本操作“拓展”是在深度上寻路，而“松弛”操作则是在广度上寻路，这就确定了贝尔曼-福特算法可以对负边进行操作而不会影响结果。

**负权环判定**

因为负权环可以无限制的降低总花费，所以如果发现第

![输入图片说明](https://images.gitee.com/uploads/images/2021/0712/142416_d13e0f9f_8927650.png "屏幕截图.png")

次操作仍可降低花销，就一定存在负权环。

**Bellman-Ford**

```java
public int networkDelayTime(int[][] times, int n, int K) {
    // 存放 K 到各个点的最短路径，最大的那个最短路径即为结果
    int[] distance = new int[ n+ 1];
    Arrays.fill(distance, Integer.MAX_VALUE);
    distance[K] = 0;//K可以是起点

    // 进行 n-1 轮的松弛，因为任意两点间的最短路径最多包含 n-1 条边
    for (int i = 1; i <= n - 1; i++) {
        for (int[] time : times) {
            // 源节点
            int u = time[0];
            // 目标节点
            int v = time[1];
            // 一个信号源从源节点到目标节点的时间
            int w = time[2];
            // 判断能否通过 u->v 缩短 distance[v]（松弛）
            if (distance[u] != Integer.MAX_VALUE) {
                //必定要更新
                if (distance[v] == Integer.MAX_VALUE) {
                    distance[v] = distance[u] + w;
                } else {
                    //判断值的大小 
                    distance[v] = Math.min(distance[v], distance[u] + w);
                }
            }
        }
    }
    return distance[n];
}
```

**SFPA算法**

- 它是 Bellman-Ford 的优化， Bellman-Ford  的时间复杂度为 O(VE)，效率太低了，SPFA 是 Bellman−Ford 的队列优化，但是算法时间效率不稳定，时间复杂度为 O(E)，最好情况下，每个节点只入队一次，就是 BFS，最坏情况下，每一个节点都要入队V−1 次，这时候就退化成 Bellman-Ford 了

- SPFA 时间复杂度某种情况下略高于 DijkstraDijkstra， 适合稀疏图。

- SPFA 是可以用于带有负权图的，在 SPFASPFA 中每一个点松弛过后说明这个点距离更近了，所以有可能通过这个点会再次优化其他点，所以它的策略是将 vis位置为 false，把这个点入队再判断一次！这就和 Dijkstra的贪心策略不同了！

- SPFA还有个用处是可以判断图是否存在负环，我们只要用一个 cnt[x] 数组来存放经过这个点的次数，上面提到过，最坏情况下每个节点入队 V-1次，如果 cnt[x] 为V 的个数，那就说明存在负环了。

```java
public int spfa(int n, int[][] edges, int start, int end){
    //这里的edges = [[begin,end,times],...]这种形式的，也可能是其他形式的，处理方式类似
    Map<Integer, ArrayList<int[]>> graph = new HashMap<>();
    for(int []edge:edges){
        int begin = edge[0];
        int endindex = edge[1];
        int time = edge[2];//这条边的权重
        if(!graph.containsKey(begin))//先判断是否存在begin的集合
            graph.put(begin,new ArrayList<int []>());
        graph.get(begin).add(new int[]{endindex,time});
    }

    // 初始化dis数组和vis数组
    int[] dist = new int[n];
    Arrays.fill(dist, Integer.MAX_VALUE);
    boolean[] visit = new boolean[n];
    dist[start] = 0;

    Queue<Integer> queue = new LinkedList<>();
    queue.offer(start);

    while (!queue.isEmpty()) {
        // 取出队首节点
        Integer poll = queue.poll();
        // 可以重复入队
        visit[poll] = false;
        // 遍历起点的邻居,更新距离
        ArrayList<int[]> list = graph.get(poll);
        if(list == null) continue;//为空直接跳过

        for (int[] arr : list) {
            int next = arr[0];
            // 如果没更新过，或者需要更新距离()
            if (dist[next] == Integer.MAX_VALUE || dist[next] > dist[poll] + arr[1]) {
                // 更新距离
                dist[next] = dist[poll] + arr[1];
                // 如果队列中没有，就不需要再次入队了 （那么判断入度可以在这里做文章）
                if (!visit[next]) {
                    visit[next] = true;
                    queue.offer(next);
                }
            }
        }
    }
    //int res = Arrays.stream(dist).max().getAsInt();

    return dist[end] == Integer.MAX_VALUE ? -1 : dist[end];
}
```



## 多源汇最短路

Floyd算法又称为插点法，是一种利用[动态规划](https://baike.baidu.com/item/动态规划/529408)的思想寻找给定的[加权图](https://baike.baidu.com/item/加权图/10579361)中多源点之间[最短路径](https://baike.baidu.com/item/最短路径/6334920)的算法，与[Dijkstra算法](https://baike.baidu.com/item/Dijkstra算法/215612)类似。（ Floyd算法 O(n^3)）



**算法过程**

1. 从任意一条单边路径开始。所有两点之间的距离是边的权，如果两点之间没有边相连，则权为无穷大。
2. 对于每一对顶点 u 和 v，看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比已知的路径更短。如果是更新它。



> 把图用邻接矩阵G表示出来，如果从Vi到Vj有路可达，则G[i][j]=d，d表示该路的长度；否则G[i][j]=无穷大。
>
> 定义一个矩阵D用来记录所插入点的信息，D[i][j]表示从Vi到Vj需要经过的点，初始化D[i][j]=j。
>
> 把各个顶点插入图中，比较插点后的距离与原来的距离，G[i][j] = min( G[i][j], G[i][k]+G[k][j] )，如果G[i][j]的值变小，则D[i][j]=k。在G中包含有两点之间最短道路的信息，而在D中则包含了最短通路径的信息。
>
> 比如，要寻找从V5到V1的路径。根据D，假如D(5,1)=3则说明从V5到V1经过V3，路径为{V5,V3,V1}，如果D(5,3)=3，说明V5与V3直接相连，如果D(3,1)=1，说明V3与V1直接相连。





```java
private int INF = 0x3f3f3f3f;

public int networkDelayTime(int[][] times, int N, int K) {
    int[][] g = new int[N + 1][N + 1];
    // 初始化图,注意,一开始距离是初始化为INF的，而不是像 spfa初始化成-1
    // spfa初始化成-1只是为了判断是否为邻居，这里初始化为INF是因为要取min的
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            g[i][j] = i == j ? 0 : 0x3f3f3f3f;
        }
    }
    for (int[] t : times) {
        g[t[0]][t[1]] = t[2];
    }
    // 使用K节点来松弛i->j的最短路径（大白话就是利用k作为中间节点）
    for (int k = 1; k <= N; k++) {
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                // 判断语句可以不用写，具体得看题目
                // if (k != i && k != j && g[i][k] != INF && g[k][j] != INF) {
                    g[i][j] = Math.min(g[i][j], g[i][k] + g[k][j]);
                // }
            }
        }
    }
    // g[a][b]表示a到b的最短距离
    // 拿结果
    int res = 0;
    for (int distance : g[K]) {
        res = Math.max(res, distance);
    }
    return res == INF ? -1 : res;
}
```



## BFS类型的题

一般是求多源的问题，大家可以直接去看LeetCode的542,994和1765。

下面给出大致的模板



```java
public int[][]bfs(int [][]mat){
    //存四个方法
    int [][]dir = new int[][]{{-1,0},{1,0},{0,-1},{0,1}};
    int m = mat.length,n = mat[0].length;
    //存结果 根据题目要求
    int [][]dist = new int[m][n];

    //所有0节点入队
    boolean [][]visit = new boolean[m][n];
    Queue<int[]> queue = new LinkedList<>();
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            //根据题目将相关位置或者点存入队列
        }
    }
    //广度遍历更新dist
    while(!queue.isEmpty()){
        int []now = queue.poll();
        int i = now[0],j = now[1];
        for(int k=0;k<4;k++){
            //遍历四个方向
            int i_new = i + dir[k][0];
            int j_new = j + dir[k][1];
            //先判断当前新位置是否符合边界条件
            if(i_new>=0 && i_new<m && j_new>=0 && j_new<n && visit[i_new][j_new]!=true){
                //相关处理 
            }
        }
    }
    return  dist;
}
```