餐饮行业做网站的好处,百度快速排名软件,西安进一步优化近期防疫措施,痘痘怎么去除效果好假期过长#xff0c;导致停更了好长时间#xff0c;复习一道算法题找找感觉。前段时间看到一篇文章#xff0c;里面提到了统治世界的十大算法#xff0c;其中之一就是迪杰斯特拉算法(Dijkstra)#xff0c;该算法主要解决的”最短路径“这一类问题。说法虽然夸张了点#… 假期过长导致停更了好长时间复习一道算法题找找感觉。前段时间看到一篇文章里面提到了统治世界的十大算法其中之一就是迪杰斯特拉算法(Dijkstra)该算法主要解决的”最短路径“这一类问题。说法虽然夸张了点但它在实际生活中确实应用广泛例如地图软件等大部分游戏中自动寻路等功能使用到的 A*搜索算法也是基于迪杰斯特拉算法优化而来。那么迪杰斯特拉算法是如何实现的呢假如我们现在有如下一个有向图图中有 6 个顶点编号分别为 1~6带有箭头的直线表示的是能从一个顶点到达另外一个顶点直线上的数字表示的是两个顶点之间的距离现在求顶点 1 到顶点 6 的最短距离。由于图中的点比较少我们直接手动计算就能算出来这个结果但是如果顶点很多有成千上万个手动计算就很难了我们只能通过程序来计算那么我们的程序该如何写呢思路从图中我们可以看到顶点 1 只能直接到达顶点 2、3、5不能直接到达顶点 6所以要想从 1 到达 6就必须得从其他顶点中转。我们定义一个数组用来表示每个顶点到顶点 1 的距离数组的索引表示的是顶点编号数组元素的值表示的是到顶点 1 的最小距离。开始我们在顶点 1 上顶点 1 能到达 2、3、5数组的状态如下。索引123456最小距离06010null50null从顶点 2 处中转顶点 2 能到达顶点 4距离为 35所以顶点 1 到顶点 4 的距离为 603595数组状态如下索引123456最小距离060109550null从顶点 3 处中转顶点 3 能到达 4距离为 30。如果通过顶点 3 中转那么 1 到达 4 的距离为 40小于经过 2 中转的距离所以数组中到顶点 4 的距离更新为 40。顶点 3 还能到达顶点 5同理通过顶点 2 中转1 到达 5 的距离为 102535小于 1 直接到达 5 的距离因此数组中到达顶点 5 的距离更新为 35更新后数组状态如下索引123456最小距离060104035null从顶点 5 中转顶点 5 能到达 2如果顶点 1 通过顶点 5 到达 2距离为 353065大于顶点 1 直接到达 2所以不更新。由于顶点 2 在前面已经遍历过它能到达哪些点了所以后面不需要再遍历它。顶点 5 还能到达顶点 6所以此时 1 到达 6 的距离为 35105140数组状态如下索引123456最小距离060104035140从顶点 4 中转顶点 4 也能达到顶点 6。如果通过顶点 4 中转那么 1 到达 6 的距离为 401555这个距离小于从 5 中转所以更新数组更新后数组状态如下索引123456最小距离06010403555以上流程就是迪杰斯特拉算法在计算最短路径问题时的核心流程。代码实现首先我们需要将这个有向图用代码表示出来通常表示图的方法有两种第一种是邻接矩阵(也就是二维数组)第二种是邻接表(也就是数组链表)这里我们选用邻接表法来表示一个有向图。另外我们还需要定义顶点之间的边一条边有起点和终点还有边的权重信息也就是长度用类 Edge 表示。代码如下private class Edge { // 起始定点 public int s; // 终止定点 public int t; // 边的权重 public int weight; Edge(int s, int t, int weight) { this.s s; this.t t; this.weight weight; }}有向图我们用类 Graph 表示类中有两个属性顶点个数 v 和描述顶点之间边的信息的数组 adj我们还提供了一个方法addEdge用来在两个顶点之间添加一条边。代码如下public class Graph { // 顶点个数(顶点编号从0开始在本文例子中编号为0的顶点不存在) private int v; // 记录每个顶点的边 private LinkedList[] adj;public Graph(int v) {this.v v;// 初始化this.adj new LinkedList[v];for (int i 0; i adj[i] new LinkedList(); } }// 添加一条边从s到达tpublic void addEdge(int s, int t, int weight) { Edge edge new Edge(s, t, weight); adj[s].add(edge); }}定义好了图的描述信息后接下来通过代码来实现迪杰斯特拉算法其代码和注释如下。有两处逻辑稍微解释一下。第一处flag 数组记录的是已经遍历过的顶点用来防止死循环例如顶点 1 能到达 2我们接着会判断 2 能到达哪些点顶点 1 又能到达 55 也能到达 2如果没有 flag 数组来记录顶点 2 我们已经遍历过了那么我们就会继续遍历 2这样会导致死循环。第二处predecessor 数组记录的是路径信息数组的索引表示的顶点编号元素的值表示的是哪一个顶点到达当前顶点的例如predecessor[3]1 表示的是通过顶点 1 到达的顶点 3。// 采用迪杰斯特拉算法找出从s到t的最短路径public void dijkstra(int s, int t) { int[] dist new int[v]; // 记录s到每个顶点的最小距离数组下标表示顶点编号值表示最小距离 boolean[] flag new boolean[v]; // 记录遍历过的顶点数组下标表示顶点编号值表示是否遍历过该顶点 for (int i 0; i dist[i] Integer.MAX_VALUE; // 初始状态下将顶点s到其他顶点的距离都设置为无穷大 } int[] predecessor new int[v]; // 记录路径索引表示顶点编号值表示到达当前顶点的顶点是哪一个 Queue queue new LinkedList(); queue.add(s); dist[s] 0; // s-s的路径为0while (!queue.isEmpty()) { Integer vertex queue.poll();if (flag[vertex]) continue; // 已经遍历过该顶点就不再遍历 flag[vertex] true;for (int i 0; i Edge edge adj[vertex].get(i);if (dist[vertex] // 如果出现了比当前路径小的方式就更新为更小路径 dist[edge.t] dist[vertex] edge.weight; predecessor[edge.t] vertex; } queue.add(edge.t); } }// 打印路径 System.out.println(最短距离 dist[t]); System.out.print(s); print(s, t, predecessor);}print 函数的作用是打印从顶点 s 到达顶点 t 的最短路径中需要经过哪些点具体代码如下就是一个递归调用比较简单// 打印路径private void print(int s, int t, int[] predecessor) { if (t s) { return; } print(s, predecessor[t], predecessor); System.out.print( - t);}测试根据文中的示例构建一个图进行结果测试代码如下public static void main(String[] args) { // 构建图 Graph graph new Graph(7); graph.addEdge(1, 2, 60); graph.addEdge(1, 3, 10); graph.addEdge(1, 5, 50); graph.addEdge(2, 4, 35); graph.addEdge(3, 4, 30); graph.addEdge(3, 5, 25); graph.addEdge(4, 6, 15); graph.addEdge(5, 2, 30); graph.addEdge(5, 6, 105); // 计算最短距离 graph.dijkstra(1, 6);}测试结果总结迪杰斯特拉算法的思想与广度优先搜索(BFS)的思路比较像每次找到自己能到达的顶点然后依次往外扩散直到遍历完所有顶点。
