JavaScript数据结构18—最短路径Dijkstra算法

Dijkstra算法的套路基本如下：想要查看某一个点和图中其他所有点的最短路径

1. 加一个和它最短路径最小的点

• 加完之后，因为添加了点，所以其他点的最短路径应该重新计算
• 回到1

//最短路径算法Dijkstra 迪杰斯特拉
//用邻接矩阵存储一个图
//顶点
function Vertex(name) {
  this.name =name;
}
//邻接矩阵
//maxvex:顶点数
function arc(maxvex){
  this.maxvex = maxvex;
  this.arcnum = 0;
  this.data = new Array(maxvex);
  for (var i = 0; i < this.data.length; i++) {
    this.data[i] = new Array(maxvex);
    for (var j = 0; j < this.data[i].length; j++) {
      this.data[i][j] = Infinity;
      if(i==j){
        this.data[i][j] = 0;
      }
    }
  }
}
//图
function Mgraph(maxvex,vertexs){
  this.arc = new arc(maxvex);
  this.vertexs = vertexs;
}
//添加边,构造无向边
Mgraph.prototype.addArc = function(start,end,length){
  var i = this.vertexs.indexOf(start);
  var j = this.vertexs.indexOf(end);
  this.arc.data[i][j] = length;
  this.arc.data[j][i] = length;
  this.arc.arcnum++;
}
Mgraph.prototype.shortPath_Dijkstra = function(v0){
  var v0_index = this.vertexs.indexOf(v0);
  var final = [];//代表当前是否计算出来了结果
  var pathmatrix = [];//最短路径下标数组
  var shortpathtable = [];//存储到各点的最短路径的权值和
  console.info('开始初始化:准备计算'+v0.name+'到各个节点的最短路径');
  for (var i = 0; i < this.arc.maxvex; i++) {
    final.push(0);
    shortpathtable.push(this.arc.data[v0_index][i]);
    pathmatrix.push(0);
  }
  shortpathtable[v0_index] = 0;
  final[v0_index] = 1;
  console.info('初始化完毕:final:'+final);
  console.info('初始化完毕:pathmatrix:'+pathmatrix);
  console.info('初始化完毕:shortpathtable:'+shortpathtable);
  var min,k;
  for (var i = 0; i < this.arc.maxvex; i++) {
    //console.info('添加一个点:'+this.vertexs[i].name+'参与计算');
    if(i == v0_index){
      continue;
    }
    min = Infinity;
    for (var w = 0; w < this.arc.maxvex; w++) {
      /**
      以下的代码用于调试
      **/
      if(!final[w]&&shortpathtable[w]<Infinity){
        console.info('发现点:'+this.vertexs[w].name+'到'+v0.name+'的最短路径是'+
          shortpathtable[w]);
      }
      if(!final[w]&&shortpathtable[w]<min){
        k=w;
        min = shortpathtable[w];
      }
    }
    console.info('没错，'+this.vertexs[k].name+'是最接近当前'+v0.name+'的');
    final[k] = 1;
    console.info('已经完成对点:'+this.vertexs[k].name+'最短路径计算');
    for (var w = 0; w < this.arc.maxvex; w++) {
      if(!final[w]&&(min+this.arc.data[k][w]<shortpathtable[w])){
        console.info('因为'+this.vertexs[k].name+'的参与,发现点:'
          +this.vertexs[w].name+'到'+v0.name+'的最短路径是'+
          (min+this.arc.data[k][w]));
        shortpathtable[w] = min+this.arc.data[k][w]
        pathmatrix[w] = k;
      }
    }
  }
  console.info(final);
  console.info(pathmatrix);
  console.info(shortpathtable);
}
//建造一个
var v0 = new Vertex('V0');
var v1 = new Vertex('V1');
var v2 = new Vertex('V2');
var v3 = new Vertex('V3');
var v4 = new Vertex('V4');
var v5 = new Vertex('V5');
var v6 = new Vertex('V6');
var v7 = new Vertex('V7');
var v8 = new Vertex('V8');
var vertexs = [v0,v1,v2,v3,v4,v5,v6,v7,v8];
var mgraph = new Mgraph(9,vertexs);
mgraph.addArc(v1,v0,10);
mgraph.addArc(v0,v5,11);
mgraph.addArc(v1,v2,18);
mgraph.addArc(v1,v8,12);
mgraph.addArc(v1,v6,16);
mgraph.addArc(v2,v8,8);
mgraph.addArc(v2,v3,22);
mgraph.addArc(v3,v8,21);
mgraph.addArc(v3,v4,20);
mgraph.addArc(v3,v7,16);
mgraph.addArc(v3,v6,24);
mgraph.addArc(v4,v7,7);
mgraph.addArc(v4,v5,26);
mgraph.addArc(v5,v6,17);
//console.info(mgraph.arc);
mgraph.shortPath_Dijkstra(v0);

output

开始初始化:准备计算V0到各个节点的最短路径
初始化完毕:final:1,0,0,0,0,0,0,0,0
初始化完毕:pathmatrix:0,0,0,0,0,0,0,0,0
初始化完毕:shortpathtable:0,10,Infinity,Infinity,Infinity,11,Infinity,Infinity,Infinity
发现点:V1到V0的最短路径是10
发现点:V5到V0的最短路径是11
没错，V1是最接近当前V0的
已经完成对点:V1最短路径计算
因为V1的参与,发现点:V2到V0的最短路径是28
因为V1的参与,发现点:V6到V0的最短路径是26
因为V1的参与,发现点:V8到V0的最短路径是22
发现点:V2到V0的最短路径是28
发现点:V5到V0的最短路径是11
发现点:V6到V0的最短路径是26
发现点:V8到V0的最短路径是22
没错，V5是最接近当前V0的
已经完成对点:V5最短路径计算
因为V5的参与,发现点:V4到V0的最短路径是37
发现点:V2到V0的最短路径是28
发现点:V4到V0的最短路径是37
发现点:V6到V0的最短路径是26
发现点:V8到V0的最短路径是22
没错，V8是最接近当前V0的
已经完成对点:V8最短路径计算
因为V8的参与,发现点:V3到V0的最短路径是43
发现点:V2到V0的最短路径是28
发现点:V3到V0的最短路径是43
发现点:V4到V0的最短路径是37
发现点:V6到V0的最短路径是26
没错，V6是最接近当前V0的
已经完成对点:V6最短路径计算
发现点:V2到V0的最短路径是28
发现点:V3到V0的最短路径是43
发现点:V4到V0的最短路径是37
没错，V2是最接近当前V0的
已经完成对点:V2最短路径计算
发现点:V3到V0的最短路径是43
发现点:V4到V0的最短路径是37
没错，V4是最接近当前V0的
已经完成对点:V4最短路径计算
因为V4的参与,发现点:V7到V0的最短路径是44
发现点:V3到V0的最短路径是43
发现点:V7到V0的最短路径是44
没错，V3是最接近当前V0的
已经完成对点:V3最短路径计算
发现点:V7到V0的最短路径是44
没错，V7是最接近当前V0的
已经完成对点:V7最短路径计算
[ 1, 1, 1, 1, 1, 1, 1, 1, 1 ]
[ 0, 0, 1, 8, 5, 0, 1, 4, 1 ]
[ 0, 10, 28, 43, 37, 11, 26, 44, 22 ]
[Finished in 0.2s]