Dijkstra算法的套路基本如下：想要查看某一個(gè)點(diǎn)和圖中其他所有點(diǎn)的最短路徑
- 加一個(gè)和它最短路徑最小的點(diǎn)
- 加完之后，因?yàn)樘砑恿它c(diǎn)，所以其他點(diǎn)的最短路徑應(yīng)該重新計(jì)算
- 回到1
//最短路徑算法Dijkstra 迪杰斯特拉
//用鄰接矩陣存儲(chǔ)一個(gè)圖
//頂點(diǎn)
function Vertex(name) {
this.name =name;
}
//鄰接矩陣
//maxvex:頂點(diǎn)數(shù)
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;
}
//添加邊,構(gòu)造無(wú)向邊
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 = [];//代表當(dāng)前是否計(jì)算出來(lái)了結(jié)果
var pathmatrix = [];//最短路徑下標(biāo)數(shù)組
var shortpathtable = [];//存儲(chǔ)到各點(diǎn)的最短路徑的權(quán)值和
console.info('開(kāi)始初始化:準(zhǔn)備計(jì)算'+v0.name+'到各個(gè)節(jié)點(diǎn)的最短路徑');
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('添加一個(gè)點(diǎn):'+this.vertexs[i].name+'參與計(jì)算');
if(i == v0_index){
continue;
}
min = Infinity;
for (var w = 0; w < this.arc.maxvex; w++) {
/**
以下的代碼用于調(diào)試
**/
if(!final[w]&&shortpathtable[w]<Infinity){
console.info('發(fā)現(xiàn)點(diǎn):'+this.vertexs[w].name+'到'+v0.name+'的最短路徑是'+
shortpathtable[w]);
}
if(!final[w]&&shortpathtable[w]<min){
k=w;
min = shortpathtable[w];
}
}
console.info('沒(méi)錯(cuò)，'+this.vertexs[k].name+'是最接近當(dāng)前'+v0.name+'的');
final[k] = 1;
console.info('已經(jīng)完成對(duì)點(diǎn):'+this.vertexs[k].name+'最短路徑計(jì)算');
for (var w = 0; w < this.arc.maxvex; w++) {
if(!final[w]&&(min+this.arc.data[k][w]<shortpathtable[w])){
console.info('因?yàn)?+this.vertexs[k].name+'的參與,發(fā)現(xiàn)點(diǎn):'
+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);
}
//建造一個(gè)
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
開(kāi)始初始化:準(zhǔn)備計(jì)算V0到各個(gè)節(jié)點(diǎn)的最短路徑
初始化完畢: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
發(fā)現(xiàn)點(diǎn):V1到V0的最短路徑是10
發(fā)現(xiàn)點(diǎn):V5到V0的最短路徑是11
沒(méi)錯(cuò)，V1是最接近當(dāng)前V0的
已經(jīng)完成對(duì)點(diǎn):V1最短路徑計(jì)算
因?yàn)閂1的參與,發(fā)現(xiàn)點(diǎn):V2到V0的最短路徑是28
因?yàn)閂1的參與,發(fā)現(xiàn)點(diǎn):V6到V0的最短路徑是26
因?yàn)閂1的參與,發(fā)現(xiàn)點(diǎn):V8到V0的最短路徑是22
發(fā)現(xiàn)點(diǎn):V2到V0的最短路徑是28
發(fā)現(xiàn)點(diǎn):V5到V0的最短路徑是11
發(fā)現(xiàn)點(diǎn):V6到V0的最短路徑是26
發(fā)現(xiàn)點(diǎn):V8到V0的最短路徑是22
沒(méi)錯(cuò)，V5是最接近當(dāng)前V0的
已經(jīng)完成對(duì)點(diǎn):V5最短路徑計(jì)算
因?yàn)閂5的參與,發(fā)現(xiàn)點(diǎn):V4到V0的最短路徑是37
發(fā)現(xiàn)點(diǎn):V2到V0的最短路徑是28
發(fā)現(xiàn)點(diǎn):V4到V0的最短路徑是37
發(fā)現(xiàn)點(diǎn):V6到V0的最短路徑是26
發(fā)現(xiàn)點(diǎn):V8到V0的最短路徑是22
沒(méi)錯(cuò)，V8是最接近當(dāng)前V0的
已經(jīng)完成對(duì)點(diǎn):V8最短路徑計(jì)算
因?yàn)閂8的參與,發(fā)現(xiàn)點(diǎn):V3到V0的最短路徑是43
發(fā)現(xiàn)點(diǎn):V2到V0的最短路徑是28
發(fā)現(xiàn)點(diǎn):V3到V0的最短路徑是43
發(fā)現(xiàn)點(diǎn):V4到V0的最短路徑是37
發(fā)現(xiàn)點(diǎn):V6到V0的最短路徑是26
沒(méi)錯(cuò)，V6是最接近當(dāng)前V0的
已經(jīng)完成對(duì)點(diǎn):V6最短路徑計(jì)算
發(fā)現(xiàn)點(diǎn):V2到V0的最短路徑是28
發(fā)現(xiàn)點(diǎn):V3到V0的最短路徑是43
發(fā)現(xiàn)點(diǎn):V4到V0的最短路徑是37
沒(méi)錯(cuò)，V2是最接近當(dāng)前V0的
已經(jīng)完成對(duì)點(diǎn):V2最短路徑計(jì)算
發(fā)現(xiàn)點(diǎn):V3到V0的最短路徑是43
發(fā)現(xiàn)點(diǎn):V4到V0的最短路徑是37
沒(méi)錯(cuò)，V4是最接近當(dāng)前V0的
已經(jīng)完成對(duì)點(diǎn):V4最短路徑計(jì)算
因?yàn)閂4的參與,發(fā)現(xiàn)點(diǎn):V7到V0的最短路徑是44
發(fā)現(xiàn)點(diǎn):V3到V0的最短路徑是43
發(fā)現(xiàn)點(diǎn):V7到V0的最短路徑是44
沒(méi)錯(cuò)，V3是最接近當(dāng)前V0的
已經(jīng)完成對(duì)點(diǎn):V3最短路徑計(jì)算
發(fā)現(xiàn)點(diǎn):V7到V0的最短路徑是44
沒(méi)錯(cuò)，V7是最接近當(dāng)前V0的
已經(jīng)完成對(duì)點(diǎn):V7最短路徑計(jì)算
[ 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]
