Как вывести кратчайший путь в графе?

Question

[nightz9r]

Есть следующий массив:

const tree = ['Moscow', [
  ['Smolensk'],
  ['Yaroslavl'],
  ['Voronezh', [
    ['Liski'],
    ['Boguchar'],
    ['Kursk', [
      ['Belgorod', [
        ['Borisovka'],
      ]],
      ['Kurchatov'],
    ]],
  ]],
  ['Ivanovo', [
    ['Kostroma'], ['Kineshma'],
  ]],
  ['Vladimir'],
  ['Tver', [
    ['Klin'], ['Dubna'], ['Rzhev'],
  ]],
]];

Я преобразовал его в список смежности:

const buildGraph = (tree, dictionary = {}, parent = null) => {
  const [node, branches] = tree;
  if (parent) dictionary[node] = [parent];
  else dictionary[node] = [];

  branches.forEach((branch) => {
    if (branch.length === 1) {
        dictionary[node].push(...branch);
        dictionary[branch[0]] = [node];
    }
    else {
      dictionary[node].push(branch[0]);
      Object.assign(dictionary, buildGraph(branch, [], node));
    }
  });
  return dictionary;
};

Вопрос: как написать алгоритм, который выводит кратчайший путь в неориентированном графе?

console.log(itinerary(tree, 'Dubna', 'Kostroma'));
// ['Dubna', 'Tver', 'Moscow', 'Ivanovo', 'Kostroma']
console.log(itinerary(tree, 'Borisovka', 'Kurchatov'));
// ['Borisovka', 'Belgorod', 'Kursk', 'Kurchatov']

Додумался только до такого алгоритма (поиск в ширину), который просто выводит true, если путь между двумя вершинами существует.

const itinerary = (tree, startPoint, endPoint) => {
  const graph = buildGraph(tree);
  const searchQueue = [];
  searchQueue.push(startPoint);
  const searched = [];
  while (searchQueue.length > 0) {
    const city = searchQueue.shift();
    if (!searched.includes(city)) {
      if (city === endPoint) {
        return true;
      }
      else {
        searchQueue.push(...graph[city]);
        searched.push(city);
      }
    }
  }
};

Comments

[Александр Талалаев]

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

Answer 1

[Wataru]

Вам надо в вашем алгоритме еще завести словарь, куда вы для каждой вершины будете складывать предыдущую в пути. Там, где вы соседнюю вершину кладете в очередь - там надо сарзу смотреть, посещенная она или нет и класть только если нет. Вот в этот момент вы знаете, что вы пришли в graph[city][i] из city.

В конце циклом по этому массиву пердыдущих вершин пройдитесь и так получите путь в обратном порядке.

Comments

[nightz9r]

Вот так переписал алгоритм

const itinerary = (tree, startPoint, endPoint) => {
  const graph = buildGraph(tree);
  const searchQueue = [];
  searchQueue.push(startPoint);
  const searched = [];
  const path = {};
  while(searchQueue.length > 0) {
		const city = searchQueue.shift()
		for(const neighbor of graph[city]) {
			if(!searched.includes(neighbor)) {
                                path[neighbor] = city;
				searchQueue.push(neighbor)
				searched.push(neighbor)
				if(neighbor === endPoint) return path;
			}
		}
  };
};

И такой объект получил на выводе для такого пути

console.log(itinerary(tree, 'Borisovka', 'Kurchatov'));
{
  Belgorod: 'Borisovka',
  Kursk: 'Belgorod',
  Borisovka: 'Belgorod',
  Voronezh: 'Kursk',
  Kurchatov: 'Kursk'
}

В объекте получил посещенные вершины ключами, а откуда посетили вершину - значениями. Что делать с этим объектом и правильный ли объект я вообще получил. Помогите, пожалуйста, разобраться

[Wataru]

Вам надо еще в самом начале в searched помещать начальную вершину.

А потом надо начать с конца и делать v = path[v], пока не придете в начало.

[nightz9r]

Удалось разобраться, спасибо! Решил задачу.

Answer 2

[Rsa97]

Задача о кратчайшем пути