单源最短路径算法-动态规划算法

/*
相比于dijdstra算法，该算法能处理负权问题。
相比于floyd算法，该算法不需要将所有顶点的最小距离计算出来，能减少复杂度。
*/
let max = Infinity;
function newGraph(){
let g1 = {
vertexs:['s','2','3','4','5','6','7','t'],
edges:[
[0,9,max,max,max,14,15,max],
[9,0,24,max,max,max,max,max],
[max,24,0,6,2,18,max,19],
[max,max,6,0,11,max,max,6],
[max,max,2,11,0,30,20,16],
[14,max,18,max,30,0,5,max],
[15,max,max,max,20,5,0,44],
[max,max,19,6,16,max,44,0]
]
};
let g2 = {
vertexs:['a','b','c','d','e','f','g'],
edges:[
[0,12,max,max,max,16,14],
[12,0,10,max,max,7,max],
[max,10,0,3,5,6,max],
[max,max,3,0,4,max,max],
[max,max,5,4,0,2,8],
[16,7,6,max,2,0,9],
[14,max,max,max,8,9,0]
]
};
let g3 = {
vertexs:['A','B','C','D','E'],
edges:[
[0,5,8,max,max],
[5,0,1,3,2],
[8,1,0,max,max],
[max,3,max,0,7],
[max,2,max,7,0]
]
};
return g3;
}
/**
清晰的体现k和k-1之间的依赖关系。
d[k][i][j]：只使用第0号到第k号点作为中间媒介时，点i到点j之间的最短路径长度。k<0表示不使用中间媒介。
d[k][i][j] = min(d[k-1][i][j], d[k-1][i][k]+d[k-1][k][j])（k,i,j∈[0,n-1]）
d[-1][i][j]=g.edges[i,j]
*/
let count = 0;
let steps = [];/*通过打印steps，我们发现很多步骤重复计算了。这时候我们可以定义一个数组，用于判断某个步骤是否执行过，执行过就不执行了。
*/
let called = ['A','B','C','D','E'].map(k=>['A','B','C','D','E'].map(i=>['A','B','C','D','E'].map(j=>false)));
function f(d,p,k,i,j){
if(called[k][i][j]){//如果是无向图，这里还可以改成called[k][i][j] || called[k][j][i],d[i][j] = d[i][k] + d[k][j];改成
d[j][i] = d[i][j] = d[i][k] + d[k][j];进一步优化性能
return;
}
count++;
called[k][i][j] = true;
steps.push({
i,j,k
});
if(k>0){
f(d,p,k-1,i,j);//d[i][j]不经过k.以0到k-1为中间媒介,计算d[i][j]
f(d,p,k-1,i,k);//d[i][j]经过k.以0到k-1为中间媒介,计算d[i][k]
f(d,p,k-1,k,j);//d[i][j]经过k.以0到k-1为中间媒介,计算d[k][j]
}
if(d[i][j] > d[i][k] + d[k][j]){
d[i][j] = d[i][k] + d[k][j];
p[i][j] = p[i][k];
}
//console.info(`i=${i},j=${j},k=${k}`);
//console.info(d);
}
function test(){
let g = newGraph();
let d = g.edges.map(item=>item.map(i=>i));
let p = g.edges.map((row,i)=>row.map((col,j)=>j));
let i=0,j=4,k=g.vertexs.length-1;
f(d,p,k,i,j);
console.info(d[i][j]);
console.info(d);
console.info(count);
console.info(p);
steps.reverse().filter(s=>s.k==0).forEach(i=>console.info(i));
}
function testall(){//求所有顶点最短路径
let g = newGraph();
let d = g.edges.map(item=>item.map(i=>i));
let p = g.edges.map((row,i)=>row.map((col,j)=>j));
let n=g.vertexs.length;
let k = n-1;
for(let i=0;i<n;i++){
for(let j=0;j<n;j++){
f(d,p,k,i,j);
}
}
console.info(d[i][j]);
console.info(d);
console.info(count);
console.info(p);
steps.reverse().filter(s=>s.k==0).forEach(i=>console.info(i));
}
//不包含终点的路径
function path(p,i,j){
let k = p[i][j];
if(k !== null){
let pik = path(p,i,k);
let pkj = path(p,k,j);
return pik.concat(pkj);
}else{
return [i];
}
}
test();

最后

以上就是现实小蚂蚁为你收集整理的单源最短路径算法-动态规划算法的全部内容，希望文章能够帮你解决单源最短路径算法-动态规划算法所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。