# 算法模板整理 **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> 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()); 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 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 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> 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()); 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 queue = new LinkedList<>(); queue.offer(start); while (!queue.isEmpty()) { // 取出队首节点 Integer poll = queue.poll(); // 可以重复入队 visit[poll] = false; // 遍历起点的邻居,更新距离 ArrayList 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 queue = new LinkedList<>(); for(int i=0;i=0 && i_new=0 && j_new