|
这篇文章主要介绍了js图数据结构处理 迪杰斯特拉算法代码实例,文中通过示例代码介绍的非常详细，对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下
/*//1、确定数据结构, mapf[i][j] 为点i到点j的距离
[
Infinity 2 5 Infinity Infinity
Infinity Infinity 2 6 Infinity
Infinity Infinity Infinity 7 1
Infinity Infinity 2 Infinity 4
Infinity Infinity Infinity Infinity Infinity
];
//2、如果源点为1，则 s = {1}, 则 v-s = {2,3,4,5}; s为已经规划好的点,v-s是需要规划的点
var dist = []; //dist[i] = mapf[1][i];dist[1] = 0;
//源点1到i有边相连，初始化前驱为1（源点为前驱），否则初始化为-1
var p = [-1,1,1,-1,-1];
//3、找到 v-s = {2，3，4，5}集合里面,到源点1，最近的点
//得出结果为2，节点为 t = 2，则 v-s={3、4、5}，s={1、2}；
//4、借道t=2，所有t的相邻点，借道t；例如相邻点3,则 a = dist[2] + maf[2][3]; b = dist[3];
//两个取较小值，得a < b; 2-3为捷径，则记录下dist[3] = a;记录下3的前驱点 p[3] = 2;
//经过第4步，计算了2的相邻点，3、4；
//5、比较v-s={3、4、5}的到源点的最近距离，即是 v-s={3、4、5}时，执行第3步，此时相当于源点为2会再次得出最小 t
//6、重复 3、4、5步*/
function Dijkstra(){
//初始化构造一个集合，mapt[i][j]为点i到j的距离,不通的为无穷大
var mapt = [
[undefined,undefined,undefined,undefined,undefined,undefined],
[undefined,Infinity,2,5,Infinity,Infinity],
[undefined,Infinity,Infinity,2,6,Infinity],
[undefined,Infinity,Infinity,Infinity,7,1],
[undefined,Infinity,Infinity,2,Infinity,4],
[undefined,Infinity,Infinity,Infinity,Infinity,Infinity],
];
var n = mapt.length - 1;
//开始计算
this.dijkstra = function(u){ //u为源点
var dist = []; //dist[i]为点i到y的最短距离
var p = []; //p[i] 为点i的前溯点
var flag = []; //flag[i] 是否已经加入 s集合
//初始化数据 dist,p,flag
for(var i = 1; i |
