在 JS 对象图中查找节点之间的路径

Question

我怎样才能得到这个结果：

[
  {Paris,Amsterdam,Berlin},
  {Paris,Bruxelles,Amsterdam,Berlin},
  {Paris,Bruxelles,Berlin}
]

来自这个数组：

[
  { HD: '9:20', V1: 'Paris', V2: 'Amsterdam', D: '3:20' },
  { HD: '8:30', V1: 'Paris', V2: 'Bruxelles', D: '1:20' },
  { HD: '10:00', V1: 'Bruxelles', V2: 'Amsterdam', D: '2:10' },
  { HD: '12:30', V1: 'Amsterdam', V2: 'Berlin', D: '6:10' },
  { HD: '11:30', V1: 'Bruxelles', V2: 'Berlin', D: '9:20' } 
]

我想映射此数组中的数据，以获取从一个城市到另一个城市的所有可能性路径，例如从 'Paris' 到 'Berlin'。

Answer 1

不使用地图函数

JS Seems to get confused with map in this case

var result = Object.keys(obj).map(function(key) {
  return [Number(key), obj[key]];
});

这里有一个使用 for 语句的方法

    var obj =    [
      { HD: '9:20', V1: 'Paris', V2: 'Amsterdam', D: '3:20' },
      { HD: '8:30', V1: 'Paris', V2: 'Bruxelles', D: '1:20' },
      { HD: '10:00', V1: 'Bruxelles', V2: 'Amsterdam', D: '2:10' },
      { HD: '12:30', V1: 'Amsterdam', V2: 'Berlin', D: '6:10' },
      { HD: '11:30', V1: 'Bruxelles', V2: 'Berlin', D: '9:20' }
    ]
    console.log(obj);
    let NewArray = [];
    for (i=0;i<obj.length ;i++){
         console.log(obj[i].HD);

        let HD = obj[i].HD;
        let V1 = obj[i].V1;
        let V2 = obj[i].V2;
        let D = obj[i].D;
        
        NewArray[i] = {HD,V1,V2,D};
    }
    console.log(NewArray);

Answer 2

输入 graph is a DAG 看起来像这样：

  +-----------------------+
  |                       |
  |                       v
Paris -> Bruxelles -> Amsterdam -> Berlin
             |                       ^
             |                       |
             +-----------------------+

我们可以构建一个对象，其中源字符串映射到其可能目的地的数组，这比输入对象使用起来更方便，然后运行每个结果路径 DFS on the graph and yield。

function *findPaths(graph, src, dst, path=[]) {
  if (src === dst) {
    yield path.concat(dst);
  }
  else if (graph[src]) {
    path.push(src);
    
    for (const neighbor of graph[src]) {
      yield *findPaths(graph, neighbor, dst, path);
    }
    
    path.pop(src);
  }
};

const graphify = routes => {
  const graph = {};
  
  for (const node of routes) {
    if (!graph[node.V1]) {
      graph[node.V1] = [];
    }
    
    graph[node.V1].push(node.V2)
  }
  
  return graph;
};

const routes = [
  { HD: '9:20', V1: 'Paris', V2: 'Amsterdam', D: '3:20' },
  { HD: '8:30', V1: 'Paris', V2: 'Bruxelles', D: '1:20' },
  { HD: '10:00', V1: 'Bruxelles', V2: 'Amsterdam', D: '2:10' },
  { HD: '12:30', V1: 'Amsterdam', V2: 'Berlin', D: '6:10' },
  { HD: '11:30', V1: 'Bruxelles', V2: 'Berlin', D: '9:20' } 
];

console.log(...findPaths(graphify(routes), "Paris", "Berlin"));

如果您预计图中会出现循环，请添加 Set 以跟踪访问过的节点以避免在遍历期间重新访问它们：

function *findPaths(graph, src, dst, path=[], visited=(new Set())) {
  if (src === dst) {
    yield path.concat(dst);
  }
  else if (graph[src] && !visited.has(src)) {
    visited.add(src);
    path.push(src);
    
    for (const neighbor of graph[src]) {
      yield *findPaths(graph, neighbor, dst, path, visited);
    }
    
    visited.delete(src);
    path.pop(src);
  }
};

const graphify = routes => {
  const graph = {};
  
  for (const node of routes) {
    if (!graph[node.V1]) {
      graph[node.V1] = [];
    }
    
    graph[node.V1].push(node.V2)
  }
  
  return graph;
};

const routes = [
  { HD: '9:20', V1: 'Paris', V2: 'Amsterdam', D: '3:20' },
  { HD: '8:30', V1: 'Paris', V2: 'Bruxelles', D: '1:20' },
  { HD: '10:00', V1: 'Bruxelles', V2: 'Amsterdam', D: '2:10' },
  { HD: '12:30', V1: 'Amsterdam', V2: 'Paris', D: '6:10' },
  { HD: '12:30', V1: 'Amsterdam', V2: 'Berlin', D: '6:10' },
  { HD: '11:30', V1: 'Bruxelles', V2: 'Berlin', D: '9:20' },
  { HD: '11:30', V1: 'Bruxelles', V2: 'Paris', D: '9:20' } 
];

console.log(...findPaths(graphify(routes), "Paris", "Berlin"));

如果您想考虑旅行时间（边权重），请使用 Dijkstra's Algorithm。实现比较复杂，因为我们需要一个优先级队列（min/Fibonacci堆）来有效地提取最短的暂定距离。

Answer 3

let data = [
    {HD: '9:20', V1: 'Paris', V2: 'Amsterdam', D: '3:20'},
    {HD: '8:30', V1: 'Paris', V2: 'Bruxelles', D: '1:20'},
    {HD: '10:00', V1: 'Bruxelles', V2: 'Amsterdam', D: '2:10'},
    {HD: '12:30', V1: 'Amsterdam', V2: 'Berlin', D: '6:10'},
    {HD: '11:30', V1: 'Bruxelles', V2: 'Berlin', D: '9:20'}
];

function getDuration(hd, d) {
    let time1 = hd.split(":");
    let time2 = d.split(":");
    let h1 = parseInt(time1[0]);
    let m1 = parseInt(time1[1]);
    let h2 = parseInt(time2[0]);
    let m2 = parseInt(time2[1]);
    if (h2 < h1) {
        h2 += 12;
    }
    let time = (h2 * 60 + m2) - (h1 * 60 + m1);
    let offset = (time % 60) * 0.01;
    return Math.floor(time / 60) + offset;
}

let mapper = {};
let durations = {};

data.forEach(item => {
    if (!mapper[item.V1]) {
        mapper[item.V1] = [];
    }
    mapper[item.V1].push(item.V2);
    durations[item.V1 + "_" + item.V2] = getDuration(item.HD, item.D);
});

let generatedRoutes = [];

function routeGenerator(starting, destination, path) {
    if (starting === destination) {
        generatedRoutes.push(path);
        return;
    }
    if (!mapper[starting]) return;
    let routes = mapper[starting];
    routes.forEach(route => {
        routeGenerator(route, destination, path + "," + route);
    })
}

routeGenerator("Paris", "Berlin", "Paris");

function calculateTimeDuration() {
    let minDuration = 100000;
    let minDurationPath = "";
    generatedRoutes.forEach(path => {
        let paths = path.split(",");
        let d = 0;
        for (let i = 0; i < paths.length - 1; i++) {
            let firstCity = paths[i];
            let secondCity = paths[i + 1];
            let key = firstCity + '_' + secondCity;
            d += durations[key];
        }
        if (d < minDuration) {
            minDuration = d;
            minDurationPath = path;
        }
    });
    return {
        duration: minDuration,
        path: minDurationPath
    }
}

console.log(calculateTimeDuration());

好的，这是一个需要解决的图形问题。首先，您需要映射从某个 V1 开始的所有路线。映射器对象包含特定路径的所有路由。

然后，只是一个普通的递归函数来生成路线。

控制台输出：

{ 
    duration: 11.4,
    path: 'Paris,Amsterdam,Berlin'
}

我已经将路径生成为字符串，您可以根据需要拆分它们并将它们推入数组。

如果您需要为任何其他入口点生成路径，您可以这样做。只需更改通过 routeGenerator 传递的参数即可。例如，如果您将其更改为，

routeGenerator("Amsterdam", "Berlin", "Amsterdam");

您将获得：

{ 
    duration: 5.4,
    path: 'Amsterdam,Berlin'
}

在 JS 对象图中查找节点之间的路径

Find paths between nodes in JS object graph

javascript

graph-theory

javascript-objects