JS使用Dijkstra算法求解最短路径

首先，迪杰斯特拉算法

Dijkstra算法是一种寻找单源点最短路径的算法。

主要观点如下：

1.顶点分为两部分：已知最短路径的顶点集Q和不可达的顶点集r。

2.定义距离数组(distance)以记录从源点到每个顶点的距离，下标表示顶点，元素值为距离。源点(起点)到自身的距离为0，源点无法到达的顶点到自身的距离为大数(如Infinity)。

3.如果顶点V与顶点W的距离加上顶点V与源点的距离小于顶点W与源点的距离，则可以更新顶点W与源点的距离，将距离数组中值非无穷大的顶点V作为过渡点。即下面的距离[v]矩阵[v] [w]距离[w]，那么距离[w]=距离[v]矩阵[v] [w]。

4.重复上一步，即遍历距离数组，不可达顶点集r为空。

第二，具体例子

偷个懒，直接用之前博客《最小生成树算法——Prim算法和Kruskal算法的JS实现》的图片做例子。

它的邻接矩阵如下：

解决步骤

第一步：假设源点为V0，最短路径的顶点集Q中只有{V0}，不可达的顶点集r中只有{V1，V2，V3，V4}。

步骤2:初始化距离数组，如下所示

第三步：取距离数组中值非无穷大的顶点为过渡点，为V0。根据距离[V]矩阵[V] [W]距离[W]的规则，那么距离[W]=距离[V]矩阵[{V0，V1，V2，V4}距离数组将变成如下，集合Q将变成

第四步：因为集合R中还有一个顶点，所以重复第三步的方法，然后改为以V1为过渡点，但是以V1为过渡点不满足距离[v]矩阵[v] [w]距离[w]，所以距离和两个集合不更新

第五步：因为集合R中还有一个顶点，所以重复第三步的方法，然后以V2为过渡点，然后发现V0到V3的距离是可以更新的，因为是2 ^ 3 ^ 9，所以更新了距离和集合。

同样的道理，穿越距离后，输出

第三，代码实现

本代码未考虑负重量，也未验证负重量。目前是按照正权重实施，然后认为是改进。

同时，这是为了找到单个源点的最短路径。如果你找到整个图的每个顶点的最短路径，你只需要遍历这些顶点，然后使用Dijkstra算法。这样，如果算上Dijkstra算法本身的时间复杂度，总复杂度将为O(n ^ 3)。

/** * Dijkstra算法：单源最短路径*思路：* 1。顶点分为两部分：知道当前最短路径的顶点集Q和无法到达的顶点集R。* 2.定义距离数组(distance)以记录从源点到每个顶点的距离，下标表示顶点，元素值为距离。源点(起点)到自身的距离为0，源点无法到达的顶点到自身的距离为大数(如Infinity)。* 3.以距离数组中值非无穷大的顶点V为过渡跳跃点，假设V跳跃到顶点W的距离加上顶点V到源点的距离小于顶点W到源点的距离，则可以更新顶点W到源点的距离。即下面的距离[v]矩阵[v] [w]距离[w]，那么距离[w]=距离[v]矩阵[v] [w]。* 4.重复上一步，即遍历距离数组，不可达顶点集r为空。* * @param矩阵邻接矩阵，表示图的起点* @param start * * * *如果想找到整个图的顶点的所有最短路径作为源点，可以使用Dijkstra算法进行遍历，但时间复杂度变成O(n ^ 3)* */函数Dijkstra(矩阵，Start=0){ const rows=matrix . length，//rows与cols相同，实际上是cols=matrix[0]的顶点数。长度；if(row！==cols | | start=rows)返回新错误(‘邻接矩阵错误或源点错误’)；//初始化距离常量距离=新数组(行)。填充(无穷大)；距离[开始]=0；for(设I=0；I行；I) {//如果(距离[I]无穷大){for(设j=0，则无法到达的顶点不能作为过渡跳跃点；j colsJ) {//例如，通过比较距离[i]矩阵[i][j]和距离[j]的大小来决定是否更新距离[j]。if(矩阵[i][j]距离[i]距离[j]) { distance[j]=矩阵[i][j]距离[I]；} } console.log(距离)；} }返回距离；}/* * *邻接矩阵*值为顶点间边的权重，0表示没有自环，大的数表示没有边(如10000) * */constmax _ integer=无穷大；//有向图中没有边或不能达到const MIN _ INTEGER=0；//没有自环常量矩阵=[[min _ integer，9，2，max _ integer，6]，[9，min _ integer，3，max _ integer，max _ integer]，[2，3，min _ integer，5，max _ integer]，[MAX_INTEGER，max _ integer，5，min _ integer，1]，[6，max _ integer，MAX_INTEGER，1，MIN _ INTEGER]]；console.log(Dijkstra(matrix，0))；//[ 0，5，2，7，6]以上就是本文的全部内容。希望对大家的学习有帮助，支持我们。