本文转载自微信公众号“bigsai”，作者：bigsai。转载本文请联系程序员bigsai公众号。前言大家好，我是bigsai，今天给大家讲讲Dijkstra算法。下次我会用这个算法来找女神，少走弯路。如果你有女朋友，你可以试试看是否有效。对于Dijkstra算法，很多人可能会觉得既熟悉又陌生，可能大多数人对bfs和dfs比较了解，但是对于dijkstra和floyd算法，可能知道它是图论中的算法，但可能不知道函数及其原理，又或者，你曾经觉得很难，那么，这个时候适合你去重新认识一下。什么是迪杰斯特拉？事实上，迪杰斯特拉（Dijkstra）是一个人，被称为结构程序设计之父。他提出了goto有害理论、信号量、原语等，创造了银行家算法、哲学家就餐问题和Dijkstra算法的解决方案。等等，1972年获得图灵奖（计算机界的诺贝尔奖），今天我们就来学习一下Dijkstra算法。Dijkstra算法有什么作用？Dijkstra是用来求单源的最短路径的，也就是计算图中一点到另一点的最短距离，为了更形象，比如你去你的鲜花女神那里手在中国情人节。如何找到没有红绿灯的最短路径？怎样才能一眼就找到最短路径呢？你需要什么算法？枚举，如果有很多这样的路径？以上图为例，如果每条路径都是已知的，那么就可以用Dijkstra算法计算出你到图中所有节点的最短距离（不过你要的是离女神最近的距离）。但是，对于这个单源最短路径，你可能会有一些疑惑：单源是什么意思？一个来源，从一个顶点开始，Dijkstra算法只能找到一个顶点到其他点的最短距离，而不能找到任何两点。最短路径和bfs有什么区别？bfs求的与其说是路径，不如说是次数。因为bfs是将相邻的点按照队列一个接一个的加入，并且两点之间没有权值或者权值相等（成本相同）。Bfs寻找最短路径。一般是没有加权路径（只代表连通性）或者权重相等，只有次数可以代表路径？最典型的案例就是迷宫问题。bfs搜索1的路径，添加一次。Dijkstra在处理具体例子上的应用还是很多的，因为具体的问题其实更有分量。例如，一个城市有多个城镇，这些城镇可能有道路，也可能没有道路。整个城镇都需要连接起来。如果要计算每个城镇到a城镇的最短路径，那么Dijkstra就派上用场了。算法分析对于一个算法，首先要了解它的运行过程。对于Dijkstra算法，首先要知道它的适用条件和环境：一个连通图，几个节点（节点可能有值），但是路径必须有值，不能为负（否则Dijkstra不适用）。Dijkstra的核心思想是贪心算法的思想，那么什么是贪心呢？贪心算法（又名贪心算法）是指在解决一个问题时，总是做出当前最好的选择。也就是说，在不考虑整体最优的情况下，他做的是某种意义上的局部最优解。贪心算法不能得到所有问题的整体最优解。关键是贪心策略的选择。所选择的贪心策略必须是无后效的，即某个状态的前一过程不会影响未来的状态，只与当前状态相关。对于贪心算法，它可以在很多情况下使用。这里有2个不恰当的例子！1、上学时，一周只能带5个苹果。如果你想带最多，那么你每次选择5个苹果。最大的一个下来五次，你选择最重的一个。2.找零，注明币值和对应的金额，以最少的金额补足一定的金额。使用贪心策略，优先选择面额大的硬币，直到收集完总量。3.活动选择问题，知道多项活动的开始时间和结束时间，想在一段时间内参加最多的活动，可以按照活动结束时间升序排列。上面的策略虽然没有很强的理论和数学基础，或者说不好解释，但更像是一个事实规律的经验，而且大部分贪心问题都需要排序，你也可能会遇到复杂的类排序规则。那么我们的Dijkstra是如何贪心的呢？对于一个点，如果没有正确的方法，确实很难计算出图中所有点的最短路径，而且如果暴力匹配的复杂度呈指数增长，也不适合解决实际问题。问题。那么我们应该怎么想呢？首先，Dijkstra算法的实现需要这些前提条件：Dijkstra处理的是权重为正的带权图，所以一个二维数组（如果空间大，就用List数组）来存储每个点对点的权重值它们之间的边（邻接矩阵或邻接表存储），每个点之间的距离被初始化为无穷大。需要一个boolean数组来判断哪些点已经确定为最短路径，哪些点没有确定。使用一个int数组来记录距离（最短路径在算法执行过程中的某些点可能会更新多次）。需要一个优先队列加入周围已经确定的点。每次抛出距离起点最短路径的点，直到所有点路径都确定为最短。简单总结流程如下：第一步一般是从选中的点（路径一般为0）开始丢入优先队列，布尔数组标记0的位置（最短的为0），然后是连接的点0左右被丢进优先级队列（可能是节点类），将每个点的距离记录到对应的数组中。这个时候周边的点只是在等待调度，可能是最短的距离，也可能会被更新。（小于则更新，大于则不动，初始第一次是无限的，一定会更新），第一次结束。从等待调度的队列中抛出距离最近的点B（第一次是0附近的邻居）。这个点的距离一定是能确定的最近的（所有值都是正数，点的距离只能越来越远？，它的路径是所有可能性中最小的）。将这个点标记为true表示已经确定，并设置这个B点的邻居加入队列（下一个等待调度的点是队列中这个点周围原有的和未确定的邻居），并在同时判断是否更新B点的邻居。确定。算法实现代码实现有点繁琐，但也不是很复杂。下面是一个Dijkstra算法的实现代码：packagegraphtheory;importjava.util.ArrayDeque;importjava.util.Comparator;importjava.util.PriorityQueue;importjava.util.Queue;导入java.util.Scanner；publicclassdijkstra{staticclassnode{intx;//节点数intlenth;//长度publicnode(intx,intlenth){this.x=x;this.lenth=lenth;}}publicstaticvoidmain(String[]args){int[][]map=newint[6][6];//记录权重，顺便记录一下链接，可以考虑加入邻接表initmap(map);//初始化booleanbool[]=newboolean[6];//判断是否intlen[]=newint[6];//lengthfor(inti=0;i<6;i++){len[i]=Integer.MAX_VALUE;}Queue
