Loading... ## Dijkstra算法 求源点到其余各点的最短距离步骤如下： 1. 用一个 dist 数组保存源点到其余各个节点的距离，dist[i] 表示源点到节点 i 的距离。初始时，dist 数组的各个元素为无穷大。用一个状态数组 state 记录是否找到了源点到该节点的最短距离，state[i] 如果为真，则表示找到了源点到节点 i 的最短距离，state[i] 如果为假，则表示源点到节点 i 的最短距离还没有找到。初始时，state 各个元素为假。  2. 源点到源点的距离为 0。即dist[1] = 0。  3. 遍历 dist 数组，找到一个节点，这个节点是：没有确定最短路径的节点中距离源点最近的点。假设该节点编号为 i。此时就找到了源点到该节点的最短距离，state[i] 置为 1。  4. 遍历 i 所有可以到达的节点 j，如果 dist[j] 大于 dist[i] 加上 i -> j 的距离，即 dist[j] > dist[i] + w[i][j]（w[i][j] 为 i -> j 的距离） ，则更新 dist[j] = dist[i] + w[i][j]。  5. 重复 3 4 步骤，直到所有节点的状态都被置为 1。  6. 此时 dist 数组中，就保存了源点到其余各个节点的最短距离。  ### 朴素版本 ```java import java.util.Arrays; import java.util.Scanner; /* 给定一个n个点m条边的 有向图 ，图中可能存在重边和自环，所有边权均为正值。 请你求出1号点到n号点的最短距离，如果无法从1号点走到n号点，则输出-1。 输入格式 第一行包含整数n和m。 接下来m行每行包含三个整数x，y，z，表示存在一条从点x到点y的有向边，边长为z。 输出格式 输出一个整数，表示1号点到n号点的最短距离。 如果路径不存在，则输出-1。 数据范围 1≤n≤500, 1≤m≤10^5, 图中涉及边长均不超过10000。 输入样例： 3 3 1 2 2 2 3 1 1 3 4 输出样例： 3 */ public class Main { //从这里看，边是比较多的，所有可以用邻接矩阵存数据 static int N = 510; static int m, n; static int[][] g = new int[N][N]; static int[] dist = new int[N]; static boolean[] st = new boolean[N]; //注意：有向图和无向图相比，无向图可以看出有向图 //如果有重边，保留距离最短的那条边 public static void main(String[] args) { Scanner sc = new Scanner(System.in); n = sc.nextInt(); m = sc.nextInt(); for (int i = 1; i <= n; i++) Arrays.fill(g[i], 0x3f3f); //权值不超过10000 while (m-- > 0) { int a = sc.nextInt(), b = sc.nextInt(), c = sc.nextInt(); g[a][b] = Math.min(g[a][b], c); } // 表示1号点到n号点的最短距离 System.out.println(dijkstra()); } private static int dijkstra() { Arrays.fill(dist, 0x3f3f); dist[1] = 0; //把自己的距离设置为 0 //遍历一遍 找到一个最小的点，加入到集合中，这里加入到集合里，是通过st来做 //迭代n次，n次迭代后获得最终结果集 for (int i = 0; i < n; i++) { int t = -1; //表示还没有最短的点 for (int j = 1; j <= n; j++) { if (!st[j] && (t == -1 || dist[t] > dist[j])) { t = j; } } //循环后找到了最短的点，为 t st[t] = true; // t 加进结果集中 //最后拿 t 更新一下结果集 for (int j = 1; j <= n; j++) dist[j] = Math.min(dist[j], dist[t] + g[t][j]); } if (dist[n] == 0x3f3f) return -1; else return dist[n]; } } ``` ### 堆优化版本 堆优化版的dijkstra是对朴素版dijkstra进行了优化，在朴素版dijkstra中时间复杂度最高的寻找距离 最短的点O(n^2)可以使用最小堆优化。 1. 一号点的距离初始化为零，其他点初始化成无穷大。 2. 将一号点放入堆中。 3. 不断循环，直到堆空。每一次循环中执行的操作为： 弹出堆顶（与朴素版diijkstra找到S外距离最短的点相同，并标记该点的最短路径已经确定）。 用该点更新临界点的距离，若更新成功就加入到堆中。 时间复杂度分析: 寻找路径最短的点：O(n)O(n) 加入集合S：O(n)O(n) 更新距离：O(mlogn) ```java import java.io.*; import java.lang.*; import java.util.*; class Main{ static int n = 0, m = 0, N = 1000010; static PriorityQueue<int[]> q = new PriorityQueue<>((a,b)->{return a[1] - b[1];});//堆 static int[] dist = new int[N];//距离数组 static boolean[] f = new boolean[N];//标记数组 static int[] h = new int[N], ne = new int[N], e = new int[N], w = new int[N];//邻接表 static int idx = 1; static int Dijkstra(){//类似广搜的过程 Arrays.fill(dist, 0x3f3f3f3f); dist[1] = 0;//初始化第一个点到自身的距离 q.offer(new int[]{1, 0}); while(q.size() != 0){ int[] a = q.poll(); int t = a[0], distance = a[1]; if(f[t])continue; f[t] = true; for(int i = h[t]; i != -1; i = ne[i]){ int j = e[i]; if(dist[j] > distance + w[i]){ dist[j] = distance + w[i]; q.offer(new int[]{j, dist[j]}); } } } if(dist[n] != 0x3f3f3f3f)return dist[n]; return -1; } static void add(int a, int b, int c){ e[idx] = b; w[idx] = c;ne[idx] = h[a]; h[a] = idx++; } public static void main(String[] args)throws Exception{ BufferedReader buf = new BufferedReader(new InputStreamReader(System.in)); String[] params = buf.readLine().split(" "); n = Integer.valueOf(params[0]); m = Integer.valueOf(params[1]); Arrays.fill(h, -1); for(int i = 1; i <= m; ++i){ String[] info = buf.readLine().split(" "); int a = Integer.valueOf(info[0]); int b = Integer.valueOf(info[1]); int c = Integer.valueOf(info[2]); add(a, b, c); } System.out.print(Dijkstra()); } } ``` ## Bellman-ford算法-含负权边 Bellman - ford 算法是求含负权图的单源最短路径的一种算法，效率较低，代码难度较小。其原理为连续进行松弛，在每次松弛时把每条边都更新一下，若在 n-1 次松弛后还能更新，则说明图中有负环，因此无法得出结果，否则就完成。 (通俗的来讲就是：假设 1 号点到 n 号点是可达的，每一个点同时向指向的方向出发，更新相邻的点的最短距离，通过循环 n-1 次操作，若图中不存在负环，则 1 号点一定会到达 n 号点，若图中存在负环，则在 n-1 次松弛后一定还会更新) 算法步骤： ```java for n次 for 所有边 a,b,w (松弛操作) dist[b] = min(dist[b],back[a] + w) ``` 注意：back[] 数组是上一次迭代后 dist[] 数组的备份，由于是每个点同时向外出发，因此需要对 dist[] 数组进行备份，若不进行备份会因此发生串联效应，影响到下一个点 ```java import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; public class Main { static int N = 510; static int M = 100010; static int n;//总点数 static int m;//总边数 static int k;//最多经过k条边 static int[] dist = new int[N];//从1到点到n号点的距离 static Node[] list = new Node[M];//结构体 static int INF = 0x3f3f3f3f; static int[] back = new int[N];//备份dist数组 public static void bellman_ford() { Arrays.fill(dist, INF); dist[1] = 0; for(int i = 0;i < k;i++) { back = Arrays.copyOf(dist, n + 1);//由于是从1开始存到n for(int j = 0;j < m;j++) { Node node = list[j]; int a = node.a; int b = node.b; int c = node.c; dist[b] = Math.min(dist[b], back[a] + c); } } if(dist[n] > INF/2) System.out.println("impossible"); else System.out.println(dist[n]); } public static void main(String[] args) throws IOException { BufferedReader reader = new BufferedReader(new InputStreamReader(System.in)); String[] str1 = reader.readLine().split(" "); n = Integer.parseInt(str1[0]); m = Integer.parseInt(str1[1]); k = Integer.parseInt(str1[2]); for(int i = 0;i < m;i++) { String[] str2 = reader.readLine().split(" "); int a = Integer.parseInt(str2[0]); int b = Integer.parseInt(str2[1]); int c = Integer.parseInt(str2[2]); list[i] = new Node(a,b,c); } bellman_ford(); } } class Node { int a, b, c; public Node(int a,int b,int c) { this.a = a; this.b = b; this.c = c; } } ``` ## SPFA算法-含负权边 明确一下松弛的概念。 考虑节点u以及它的邻居v，从起点跑到v有好多跑法，有的跑法经过u，有的不经过。经过u的跑法的距离就是distu+u到v的距离。所谓松弛操作，就是看一看distv和distu+u到v的距离哪个大一点。如果前者大一点，就说明当前的不是最短路，就要赋值为后者，这就叫做松弛。 **spfa算法文字说明：** 1. 建立一个队列，初始时队列里只有起始点。 2. 再建立一个数组记录起始点到所有点的最短路径（该表格的初始值要赋为极大值，该点到他本身的路径赋为0）。 3. 再建立一个数组，标记点是否在队列中。 4. 队头不断出队，计算始点起点经过队头到其他点的距离是否变短，如果变短且被点不在队列中，则把该点加入到队尾。 5. 重复执行直到队列为空。 6. 在保存最短路径的数组中，就得到了最短路径。 图解：  1. 源点A首先入队，然后A出队，计算出到BC的距离会变短，更新距离数组，BC没在队列中，BC入队  2. B出队，计算出到D的距离变短，更新距离数组，D没在队列中，D入队。然后C出队，无点可更新。  3. D出队，计算出到E的距离变短，更新距离数组，E没在队列中，E入队。  4. E出队，此时队列为空，源点到所有点的最短路已被找到，A->E的最短路即为8  ```java /* 适用范围：只要没有负环，都可以使用。 spfa也能解决权值为正的图的最短距离问题，且一般情况下比Dijkstra算法还好 时间复杂度：一般情况 O(m) 1. 初始化dist[1]=0; dist[其他点] = 正无穷 2. 队列不空 1. 只有这个点被更新后，其他与它相连的点才会被更新 */ import java.util.*; public class Main { static int N = 100010; static int n, m; // 采用邻接表来存储稀疏图。因为是稀疏图点比较多 static int h[] = new int[N], e[] = new int[N], ne[] = new int[N], w[] = new int[N], idx = 0; // dist[i]: i表示离1号点的距离 static int[] dist = new int[N]; // st集合：防止队列存储重复的点的编号 static boolean[] st = new boolean[N]; // 用INF表示正无穷 static int INF = 0x3f3f3f3f; // 采用数组模拟队列 static int[] q = new int[N]; // idx可以看成表示的是边 static void add(int a, int b, int c) { e[idx] = b; // 权重 w[idx] = c; ne[idx] = h[a]; h[a] = idx ++; } static int spfa() { // 初始化距离为INF Arrays.fill(dist, INF); // 初始化第一个点为0 dist[1] = 0; // 定义一个队列,队列里面存储的是节点的编号 int hh = 0, tt = -1; // 加入1号点 q[++ tt] = 1; // 当队列不为空，就一直循环，队列里面存储的是被更新过的节点， // 只有被更新过的节点才可能更新与它相连的节点 while (hh <= tt) { // 取出队头元素 int t = q[hh ++]; // 标志为false，让这个点可以再次加入队列 st[t] = false; /* 重边不会被影响到，dist数组里面最后肯定是存储最小的，而且队列里面存储的点的编号， * 在最终更新其他点的时候，是用的肯定是最小的dist[i] * * 因为队头这个点被更新过，所以与它相连的其他点的距离可能也会被更新。 */ for(int i = h[t]; i != -1; i = ne[i]) { int j = e[i]; if(dist[j] > dist[t] + w[i]) { dist[j] = dist[t] + w[i]; // 如果这个点没有加入队列，这里是防止点重复被加入。加快执行速度 if(!st[j]) { q[++ tt] = j; // 标志这个点已经被加入队列 st[j] = true; } } } } // 如果这个点不可达，就一定不会被更新，哪怕有一个点和他相连， // 但是相连的那个点是不可达的，所以这个点也不会被更新。 if (dist[n] == INF) return -1; return dist[n]; } public static void main(String[] args) { Scanner sc = new Scanner(System.in); n = sc.nextInt(); m = sc.nextInt(); // 初始化 Arrays.fill(h, -1); while(m -- > 0) { int a = sc.nextInt(), b = sc.nextInt(), c = sc.nextInt(); // 这里可以不用管重边。原因在上面的for循环 add(a, b, c); } int t = spfa(); if (t == -1) System.out.println("impossible"); else System.out.println(t); } } ``` 是否包含负环判断 ```java import java.util.Arrays; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class Main { static int N = 100010, V = 0x3f3f3f3f; static int n, m; static int[] h = new int[N], w = new int[N], e = new int[N], ne = new int[N]; static int idx; static int[] dist = new int[N], cnt = new int[N]; static boolean[] st = new boolean[N]; private static void add(int a, int b, int c) { e[idx] = b; w[idx] = c; ne[idx] = h[a]; h[a] = idx ++; } private static boolean spfa() { Queue<Integer> queue = new LinkedList<>(); for (int i = 1; i <= n; i ++) { st[i] = true; queue.offer(i); } while (!queue.isEmpty()) { int t = queue.poll(); st[t] = false; for (int i = h[t]; i != -1; i = ne[i]) { int j = e[i]; if (dist[j] > dist[t] + w[i]) { dist[j] = dist[t] + w[i]; cnt[j] = cnt[t] + 1; if(cnt[j] >= n) return true; if(!st[j]) { st[j] = true; queue.offer(j); } } } } return false; } public static void main(String[] args) { Scanner sc = new Scanner(System.in); n = sc.nextInt(); m = sc.nextInt(); Arrays.fill(h, -1); while (m -- > 0) { int a = sc.nextInt(); int b = sc.nextInt(); int c = sc.nextInt(); add(a, b, c); } if (spfa()) System.out.println("Yes"); else System.out.println("No"); } } ``` ## Floyd算法 动态规划思想 ```java import java.util.Scanner; /* 给定一个n个点m条边的有向图，图中可能存在重边和自环，边权可能为负数。 再给定k个询问，每个询问包含两个整数x和y，表示查询从点x到点y的最短距离，如果路径不存在，则输出“impossible”。 数据保证图中不存在负权回路。 输入格式 第一行包含三个整数n，m，k 接下来m行，每行包含三个整数x，y，z，表示存在一条从点x到点y的有向边，边长为z。 接下来k行，每行包含两个整数x，y，表示询问点x到点y的最短距离。 输出格式 共k行，每行输出一个整数，表示询问的结果，若询问两点间不存在路径，则输出“impossible”。 数据范围 1≤n≤200, 1≤k≤n^2 1≤m≤20000, 图中涉及边长绝对值均不超过10000。 输入样例： 3 3 2 1 2 1 2 3 2 1 3 1 2 1 1 3 输出样例： impossible 1 */ public class Main { /*解题思路，动态规划的思想 假设节点序号是从1到n。 假设f[0][i][j]是一个n*n的矩阵，第i行第j列代表从i到j的权值，如果i到j有边，那么其值就为ci,j（边ij的权值）。 如果没有边，那么其值就为无穷大。 f[k][i][j]代表（k的取值范围是从1到n），在考虑了从1到k的节点作为中间经过的节点时，从i到j的最短路径的长度。 比如，f[1][i][j]就代表了，在考虑了1节点作为中间经过的节点时，从i到j的最短路径的长度。 分析可知，f[1][i][j]的值无非就是两种情况，而现在需要分析的路径也无非两种情况，i=>j，i=>1=>j： 【1】f[0][i][j]：i=>j这种路径的长度，小于，i=>1=>j这种路径的长度 【2】f[0][i][1]+f[0][1][j]：i=>1=>j这种路径的长度，小于，i=>j这种路径的长度 形式化说明如下： f[k][i][j]可以从两种情况转移而来： 【1】从f[k−1][i][j]转移而来，表示i到j的最短路径不经过k这个节点 【2】从f[k−1][i][k]+f[k−1][k][j]转移而来，表示i到j的最短路径经过k这个节点 总结就是：f[k][i][j]=min(f[k−1][i][j],f[k−1][i][k]+f[k−1][k][j]) 从总结上来看，发现f[k]只可能与f[k−1]有关。 */ static int N = 210; static int n, m, q; static int[][] d = new int[N][N]; static int INF = (int)1e9; public static void main(String[] args) { Scanner sc = new Scanner(System.in); n = sc.nextInt(); m = sc.nextInt(); q = sc.nextInt(); for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { if (i == j) d[i][j] = 0; else d[i][j] = INF; } } for(int i = 0; i < m; i++) { int a = sc.nextInt(), b = sc.nextInt(), w = sc.nextInt(); d[a][b] = Math.min(d[a][b], w); } Floyd(); while (q-- > 0) { int a = sc.nextInt(), b = sc.nextInt(); if (d[a][b] > INF / 2) System.out.println("impossible"); else System.out.println(d[a][b]); } } private static void Floyd() { for (int k = 1; k <= n; k++) { for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { d[i][j] = Math.min(d[i][j], d[i][k] + d[k][j]); } } } } } ``` 最后修改：2023 年 04 月 01 日 © 允许规范转载 赞 1 如果觉得我的文章对你有用，请随意赞赏
1 条评论
可以的