Implementation of the algorithm for finding the shortest path in width on JS

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

I have such an implementation(the case with a directed graph), which allows you to find the nearest element you are looking for, and it is also easy to convert it to find the length of the shortest path, but I can not understand how to save the shortest path. it would be interesting to see solutions for the directed and undirected graph.

Author: Uzakov Nikita, 2020-04-19
Source

1 answers

I managed to write a crutch(using the lecture: https://www.youtube.com/watch?v=S-hjsamsK8U&list=RDsBJ7ana1fgI&index=2), which works, may be useful to someone:

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')
 0
Author: Uzakov Nikita, 2020-04-19 11:54:46