@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);
      }
    }
  }
};
  • Вопрос задан
  • 144 просмотра
Решения вопроса 1
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, экс-олимпиадник.
Вам надо в вашем алгоритме еще завести словарь, куда вы для каждой вершины будете складывать предыдущую в пути. Там, где вы соседнюю вершину кладете в очередь - там надо сарзу смотреть, посещенная она или нет и класть только если нет. Вот в этот момент вы знаете, что вы пришли в graph[city][i] из city.

В конце циклом по этому массиву пердыдущих вершин пройдитесь и так получите путь в обратном порядке.
Ответ написан
Пригласить эксперта
Ответы на вопрос 1
Rsa97
@Rsa97
Для правильного вопроса надо знать половину ответа
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы