Найти пути между узлами в графе объектов 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' } 
]

Я хочу отобразить данные из этого массива, чтобы получить все возможности путей, из которых можно получитьнапример, из города в Париж, из Берлина.

Answer 1

Входные данные graph являются DAG и выглядят так:

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

Мы можем построить объект с исходными строками, сопоставленными с массивом их возможныхадресаты, которые намного удобнее использовать, чем входной объект, затем запустите DFS на графике и получите каждый путь к результату.

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, visited);
    }
    
    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"));

Если вы хотите учесть время в пути (вес ребер), используйте Алгоритм Дейкстры . Реализация более сложна, потому что нам нужна очередь приоритетов (min / Fibonacci heap) для эффективного извлечения кратчайшего пробного расстояния.

Answer 2

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. объекты mapper содержат все маршруты для определенного пути.

затем просто обычная рекурсивная функция для генерации маршрутов.

Консольный вывод:

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

Я сгенерировалпути в виде строки, и вы можете разделить их, если вам нужно, и поместить их в массив.

если вам нужно сгенерировать пути для любой другой точки входа, вы можете сделать это. Просто измените параметры, проходящие через routeGenerator. Например, если вы измените его на

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

, вы получите:

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

Answer 3

Без использования карты. Функция

JS. В данном случае кажется, что путают с картой

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);