這篇文章主要介紹了js圖數(shù)據(jù)結(jié)構(gòu)處理 迪杰斯特拉算法代碼實(shí)例,文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下
/*//1、確定數(shù)據(jù)結(jié)構(gòu), mapf[i][j] 為點(diǎn)i到點(diǎn)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、如果源點(diǎn)為1，則 s = {1}, 則 v-s = {2,3,4,5}; s為已經(jīng)規(guī)劃好的點(diǎn),v-s是需要規(guī)劃的點(diǎn)
var dist = []; //dist[i] = mapf[1][i];dist[1] = 0;
//源點(diǎn)1到i有邊相連，初始化前驅(qū)為1（源點(diǎn)為前驅(qū)），否則初始化為-1
var p = [-1,1,1,-1,-1];
//3、找到 v-s = {2，3，4，5}集合里面,到源點(diǎn)1，最近的點(diǎn)
//得出結(jié)果為2，節(jié)點(diǎn)為 t = 2，則 v-s={3、4、5}，s={1、2}；
//4、借道t=2，所有t的相鄰點(diǎn)，借道t；例如相鄰點(diǎn)3,則 a = dist[2] + maf[2][3]; b = dist[3];
//兩個(gè)取較小值，得a < b; 2-3為捷徑，則記錄下dist[3] = a;記錄下3的前驅(qū)點(diǎn) p[3] = 2;
//經(jīng)過第4步，計(jì)算了2的相鄰點(diǎn)，3、4；
//5、比較v-s={3、4、5}的到源點(diǎn)的最近距離，即是 v-s={3、4、5}時(shí)，執(zhí)行第3步，此時(shí)相當(dāng)于源點(diǎn)為2會(huì)再次得出最小 t
//6、重復(fù) 3、4、5步*/
function Dijkstra(){
//初始化構(gòu)造一個(gè)集合，mapt[i][j]為點(diǎn)i到j(luò)的距離,不通的為無窮大
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;
//開始計(jì)算
this.dijkstra = function(u){ //u為源點(diǎn)
var dist = []; //dist[i]為點(diǎn)i到y(tǒng)的最短距離
var p = []; //p[i] 為點(diǎn)i的前溯點(diǎn)
var flag = []; //flag[i] 是否已經(jīng)加入 s集合
//初始化數(shù)據(jù) dist,p,flag
for(var i = 1; i <= n; i++){
dist[i] = mapt[u][i]; //從源點(diǎn)到i的距離
if(dist[i] == Infinity){ //前溯點(diǎn)如果不通過為-1
p[i] = -1;
}else{
p[i] = u;
}
flag[i] = false; //都沒有選中
}
flag[u] = true; //選擇了源點(diǎn)，s集合只有 u
for(var i = 1; i <= n; i++){
var t = u; var temp = Infinity;
for(var j = 1; j <= n ; j++){ //獲取dist里面，v-s集合的最短距離
if(!flag[j] && dist[j] <= temp){
temp = dist[j];
t = j;
}
}
//查看是否找到最短的距離
if(t == u){
return {
dist:dist,
p:p
};
}
//找到了,將t加入集合 s
flag[t] = true;
for(var k = 1 ; k <= n; k++){ //以t為捷徑點(diǎn)(t為前溯點(diǎn))，尋找所有滿足條件的點(diǎn)
if(!flag[k] && mapt[t][k] < Infinity ){
if(dist[k] > (dist[t] + mapt[t][k])){
dist[k] = dist[t] + mapt[t][k]; //源點(diǎn)到k的距離 > 源點(diǎn)到t的距離 + t到k的距離
p[k] = t;
}
}
}
}
return {
dist:dist,
p:p
}
}
this.getpath = function(u){
var process = this.dijkstra(u);
var dist = process.dist;
var p = process.p;
for(var i = 1; i <= n; i++){
var start = i;
var str = i;
while(start != -1){
start = p[start]; //迭代出路徑
if(start != -1){
str = str + '、' + start;
}
}
console.log(str);
}
}
}
var Dijk = new Dijkstra();
//console.log(Dijk.dijkstra(1));
console.log(Dijk.getpath(1));
聲明：本網(wǎng)頁內(nèi)容旨在傳播知識(shí)，若有侵權(quán)等問題請及時(shí)與本網(wǎng)聯(lián)系，我們將在第一時(shí)間刪除處理。TEL:177 7030 7066 E-MAIL:11247931@qq.com
