Реализация алгоритма поиска кратчайшего пути в ширину на JS

Question

const graph = {
  you: ['alice', 'bob', 'claire'],
  bob: ['anuj', 'peggy'],
  alice: ['peggy'],
  claire: ['thom']
  anuj: [],
  peggy: [],
  thom: [],
  johny: [],
}
//push shift
const isSeller = name => name === 'thom';
const addDeque = (friends, deque) => {
  for (i=0; i<friends.length; i+=1) {
    deque.push(friends[i])
  }
}
const search = (name) => {
  const visited = [];
  const deque = []
  addDeque(graph['you'], deque);
  while (deque.length>0) {
    const person = deque[0];
    deque.shift();
    if (!visited.includes(person)) {
      visited.push(person)
      if (isSeller(person)){
        console.log(person)
        return true
      }
      addDeque(graph[person], deque);
    }      
  }
  return false;
}

имею такую реализацию(случай с ориентированным графом), которая позволяет находить искомый ближайший элемент, так-же её легко преобразовать для нахождения длины кратчайшего пути, но никак не могу понять как сохранить кратчайший путь. интересно было бы увидеть решения для ориентированного и неориентированного графа.

Answer 1

Удалось написать костыль(с помощью лекции: https://www.youtube.com/watch?v=S-hjsamsK8U&list=RDsBJ7ana1fgI&index=2), который работает, возможно будет кому-то полезно:

const graph = {
  you: ['alice', 'bob', 'claire'],
  claire: ['thom', 'johny'],
  bob: ['anuj', 'peggy'],
  alice: ['peggy'],
  anuj: [],
  peggy: [],
  thom: [],
  johny: []
}

const aa = (end_vertex) => {
  const startPoint = 'you'; // начальная точка графа(исток)
  const parents = {}; // объект с родителями, используется для построения кратчайшего пути
  const distances = { // объект с дистанцией, используется для определения дублирования захода в точку и расчета длины пути, по необходимости
    [startPoint]: 0 //нулеввая длина от начальной точки до неё самой
  };
  const queue = [startPoint]; // очередь для работы алгоритма, в нее складываем все элементы и извлекаем из неё
  while (queue.length>0) { // пока очередь имеет хоть один элемент цикл будет повторяться
    const currentFromQueue = queue[0]; //извлекаем первый элемент из очереди, на первой итерации он будет 'you'
    queue.shift(); //удаляем первый элемент сверху очереди
    for (let iter of graph[currentFromQueue]) { // для всех потомков рассматриваемого элемета
      if (!distances[iter]) {  // если дистанция нулевая(в точку еще не заходили)
        distances[iter] = distances[currentFromQueue]+1; // добавляем длину дистанции для рассматриваемого потомка 
        queue.push(iter) // добавляем потомка в очередь
        parents[iter] = currentFromQueue; // добавляем в массив родителей информацию о том, что текущий потомок наследуется от рассматриваемого родителя
      } 
    }
  }
  const path = [end_vertex]; // начало пути с конца
  let parent = parents[end_vertex]; // берем первого родителя потомка
  while (!!parent) { // пока родители существуют 
    path.push(parent); //добавляем родителя в путь
    parent = parents[parent] // ищем родителя у текущего родителя
  }
  path.reverse() // реверсируем путь
  console.log(path)
}

aa('peggy')

БЛОГ НА HUSL

Реализация алгоритма поиска кратчайшего пути в ширину на JS

Ответы (1 шт):