JS实现深度优先搜索求解两点间最短路径

Winola ·
更新时间:2024-11-13
· 597 次阅读

本文实例为大家分享了JS实现深度优先搜索求解两点间最短路径的具体代码,供大家参考,具体内容如下

效果:

找出图里点到点最短路径,并打印轨迹

图片如下所示:


代码:

const map = [ [0, 1, 1, 0, 1], [1, 0, 0, 1, 0], [1, 0, 0, 0, 1], [0, 1, 0, 0, 0], [1, 0, 1, 0, 0] ] function dfsManager(map, start, end){ var min = 9999, path = [], unvisited = []; for(let i=0; i<5;i++){ unvisited[i] = true } (function dfs(map, start, end, step){ //unvisited[start] = false //不重复访问最后的节点 if(start === end){ console.log('step:',step) for(let i=0; i<path.length; i++){ if(path[i] >= 0){ console.log(path[i]+'->') } } if(min > step){ min = step } return } unvisited[start] = false //要重复访问最后的节点 let len = map.length for(let i=0; i<len; i++){ if(map[start][i] === 1 && unvisited[i]){ path.push(i) //记录路径 dfs(map, i, end, step+1) path.pop() //避免污染其他路径 } } })(map, start, end, 0) return min } console.log('min:',dfsManager(map,3,4))

output:

step: 4
1->
0->
2->
4->
step: 3
1->
0->
4->
min: 3



js实现 深度优先搜索 js 最短路径

需要 登录 后方可回复, 如果你还没有账号请 注册新账号