Использование функции Boost graph width_first_search() для поиска пути в невзвешенном неориентированном графе

Question

Я использую граф adjacency_list с неориентированными и невзвешенными ребрами.Мне нужно найти кратчайший путь между вершиной u и вершиной v.Должен ли я использовать width_first_search(), начиная с u?При достижении v, как мне получить путь и как мне остановить поиск?

Спасибо!

Answer 1

Вы должны использовать один из алгоритмов кратчайшего пути, Кратчайший Путь Дейкстры является наиболее подходящим, так как вам нужно найти путь всего между двумя вершинами.Существует пример за его использование в дистрибутиве boost.Существует несколько вариантов получения выходных данных из этой функции:либо предоставив карту удаленности объекта, либо создав карту предшественника, либо написав имя пользовательского посетителя.

Answer 2

Да, выполните функцию width_first_search(), начиная с u .

FOR every vertex i meet
  IF i==v: BREAK
  record predecessor of i as i.p

Чтобы найти кратчайший путь, начните с v:

PRINT_PATH(u, v)
  IF v==u
    print u
  ELSEIF v.p==NIL
    print 'no path from u to v exists'
  ELSE PRINT_PATH(u, v.p)
    print v

Answer 3

Вам нужно использовать минимальное связующее дерево:алгоритм поиска.Это довольно простой прямолинейный жадный алгоритм.