Dijkstra算法的套路基本如下：想要查看某一个点和图中其他所有点的最短路径
- 加一个和它最短路径最小的点
- 加完之后，因为添加了点，所以其他点的最短路径应该重新计算
- 回到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]
