脚本宝典收集整理的这篇文章主要介绍了js实例教程-JavaScript与Dijkstra最短路算法代码教程，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。

 //求解index号顶点到达其他顶点的最短距离 function dijkstra(path,index){     VAR m = path && path.length;     var n = m &amp;& path[0].length;      if(m && n && m===n && index < n){         //初始化distance         var dis = [];         var i;         for(i = 0; i< n;i++){             dis.push(path[index][i]);         }         var flag = [];//用于标识index号至其他顶点的距离是否确定         for(i = 0; i < n; i++ ){             flag.push(false)         }         flag[index] = true;          var min,minIndex;         for(i = 0;i < n;i++){             min = Infinity;             //找出剩余的不确定的点到index最短的距离对应的索引             for(var j = 0; j < n; j++){                 if(!flag[j] && dis[j] < min){                     min = dis[j];                     minIndex = j;                 }             }             flag[minIndex] = true;//标识index到此顶点的距离已经确认             for(var k = 0; k < n; k++){                 //判断minIndex到k之间有无道路                 if(path[minIndex][k] < Infinity){                     //更新distance                     if(dis[k] > dis[minIndex] + path[minIndex][k]){                         dis[k] = dis[minIndex] + path[minIndex][k];                     }                 }             }         }         return dis;     }     else{         throw new Error("数据有误")     } }

背景

Floyd 最短路算法用于求解任意两点的最短路径，称为“多源最短路”。下面我们介绍指定一个点到其他各个顶点的最短路径，叫做：单源最短路径。

下面我们还是先给出本篇文章讲解依赖的图：

数据结构

同样，我们使用一个二维数组存储上述图的信息。

求解过程

根据上图：我们可以得到初始矩阵path：

前面我们说过dijkstra是“单源最短路径”，在讲解求解过程之前，我们就选择0号顶点作为源点。

选择好了源点，我们还需要一个一维数组用来存储源点到各个顶点的距离，

如下为初始值：

此时我们称dis数组为最短路的“估计值”。

下面我们根据上述信息，一步步的去更新dis数组，得到最后的结果。

计算过程

既然是求0号顶点到其他顶点的最短距离，那我们首先根据dis数组，找出当前距离0号顶点最近的一个顶点，我们可以找到1号顶点距离0号顶点最近。此时，我们就可以确定0号顶点到1号顶点最短距离。也就是说dis[1]从估计值变成了确定值。这个时候你可能会想为什么？我们可以这样思考，找最短路径的途径就是看能不能找到中转点从而减少距离，由于我们取得是dis中的最小值，那么不可能再找到中转点从而减少0到1的距离。

既然我们已经确认了0号到1号的最短距离，这个时候我们就去更新我们的dis数组，如何更新呢？我们可以把1号顶点作为中转点，通过查看初始矩阵path，通过比较dis[1] + path[1][i]和dis[i]的大小来决定是否更新dis[i]。更新结束之后，我们得到：

更新完dis之后，依据更新的dis，从未确定距离的点中选出距离最短的那个，这个距离就变成了确定值，紧接着去更新dis数组。得到：

紧接着重复执行上述动作，依次得到更新的dis数组为：

最后一张图，就是最后的结果。

总结

根据上述流程，我们做出如下总结：

将所有的顶点分为两个部分：已知最短距离的顶点集合P和未知最短距离的顶点集合Q。最开始的时候，已知最短距离的顶点集合中只有源点。 初始化dis数组，将源点s到自己的距离设置为0。如果存在源点能够直接到达的顶点i，那么将dis[i]设置为path[s][i]，否则设置为Infinity。 依据dis数组，在未知顶点集合Q中选出距离源点最近的一个顶点u，放入P中，并考察所有以u为起点的边，以u作为中转点，检验是否能够减短源点到其他点的距离。如果有，就更新dis数组。

重复上一步骤，直到Q中没有顶点。

完整代码

 //求解index号顶点到达其他顶点的最短距离 function dijkstra(path,index){     var m = path && path.length;     var n = m && path[0].length;      if(m && n && m===n && index < n){         //初始化distance         var dis = [];         var i;         for(i = 0; i< n;i++){             dis.push(path[index][i]);         }         var flag = [];//用于标识index号至其他顶点的距离是否确定         for(i = 0; i < n; i++ ){             flag.push(false)         }         flag[index] = true;          var min,minIndex;         for(i = 0;i < n;i++){             min = Infinity;             //找出剩余的不确定的点到index最短的距离对应的索引             for(var j = 0; j < n; j++){                 if(!flag[j] && dis[j] < min){                     min = dis[j];                     minIndex = j;                 }             }             flag[minIndex] = true;//标识index到此顶点的距离已经确认             for(var k = 0; k < n; k++){                 //判断minIndex到k之间有无道路                 if(path[minIndex][k] < Infinity){                     //更新distance                     if(dis[k] > dis[minIndex] + path[minIndex][k]){                         dis[k] = dis[minIndex] + path[minIndex][k];                     }                 }             }         }         return dis;     }     else{         throw new Error("数据有误")     } }

觉得可用，就经常来吧！Javascript技巧 脚本宝典 欢迎评论哦！ js技巧，巧夺天工，精雕玉琢。小宝典献丑了！

脚本宝典总结

以上是脚本宝典为你收集整理的js实例教程-JavaScript与Dijkstra最短路算法代码教程全部内容，希望文章能够帮你解决js实例教程-JavaScript与Dijkstra最短路算法代码教程所遇到的问题。

如果觉得脚本宝典网站内容还不错，欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。