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

2019-11-19 12:16:45

字体：大中小

来源：转载

供稿：网友

本文实例为大家分享了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：