查找对象数组最短路径在JavaScript

Question

我有对象数组像

const obs = [ 
    { from: "A", to: "C", dis: 5}, 
    { from: "A", to: "D", dis: 4}, 
    { from: "D", to: "C", dis: 8}, 
    { from: "C", to: "B", dis: 9}, 
    { from: "B", to: "D", dis: 17}, 
] 

现在我已经从A找到B. 最短路径dis所以FR我已创建二维数组

的距离矩阵

findUniqueEndPoints() { 

     let _endPoints = [] 
     obs.forEach(e => { 
      if (!_endPoints.includes(e.from)) { 
       _endPoints.push(e.from) 
      } 
      if (!_endPoints.includes(e.to)) { 
       _endPoints.push(e.to) 
      } 

     }) 
     return _endPoints 
    } 

    this.endPoints = this.findUniqueEndPoints() 
    let _matrix = [] 
    this.endPoints.forEach((e, i) => { 
     //const valus = obs.map(o => o.from === e ? o.dis : null) 
     _matrix[i] = this.endPoints.map(() => 0) 
    }) 

    obs.forEach(e => { 
     _matrix[this.endPoints.indexOf(e.from)][this.endPoints.indexOf(e.to)] = e.dis 
    }) 
    console.log(_matrix) 
    // logs 
    //[[0, 5, 4, 0][0, 0, 0, 9][0, 8, 0, 0][0, 0, 17, 0]] 

Answer 1

使用djikstra寻路状的逻辑，在地图上标注的步骤，以各点，同时保持轨道路径的它：

var obs = [ 
 
    { from: "A", to: "C", dis: 5 }, 
 
    { from: "A", to: "D", dis: 4 }, 
 
    { from: "D", to: "C", dis: 8 }, 
 
    { from: "C", to: "B", dis: 9 }, 
 
    { from: "B", to: "D", dis: 17 }, 
 
]; 
 
function findPath(from, to) { 
 
    var open = obs 
 
     .filter(function (part) { 
 
     return part.from == from || part.to == from; 
 
    }); 
 
    var dict = {}; 
 
    dict[from] = { dis: 0, path: from }; 
 
    obs 
 
     .filter(function (part) { 
 
     return part.from == from || part.to == from; 
 
    }) 
 
     .forEach(function (v, i) { 
 
     if (dict[v.to] === void 0) { 
 
      dict[v.to] = { dis: v.dis, path: from + v.to }; 
 
     } 
 
     else if (dict[v.to].dis > v.dis) { 
 
      dict[v.to] = { dis: v.dis, path: from + v.to }; 
 
     } 
 
    }); 
 
    while (dict[to] === void 0) { 
 
     for (var key in dict) { 
 
      if (dict.hasOwnProperty(key)) { 
 
       var closed = dict[key]; 
 
       obs 
 
        .filter(function (part) { 
 
        return part.from == key || part.to == key || part.from == key || part.to == key; 
 
       }) 
 
        .forEach(function (v, i) { 
 
        var c = v.dis + closed.dis; 
 
        if (dict[v.to] === void 0) { 
 
         dict[v.to] = { dis: c, path: closed.path + v.to }; 
 
        } 
 
        else if (dict[v.to].dis > c) { 
 
         dict[v.to] = { dis: c, path: closed.path + v.to }; 
 
        } 
 
        if (dict[v.from] === void 0) { 
 
         dict[v.from] = { dis: c, path: closed.path + v.to }; 
 
        } 
 
        else if (dict[v.from].dis > c) { 
 
         dict[v.from] = { dis: c, path: closed.path + v.to }; 
 
        } 
 
       }); 
 
      } 
 
     } 
 
    } 
 
    return dict[to]; 
 
} 
 
//TEST 
 
var path = findPath("A", "B"); 
 
console.log(path);