Используя график Boost breadth_first_search (), чтобы найти путь в невзвешенном, неориентированном графе

Question

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

спасибо!

Answer 1

Да, выполните breadth_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 2

Вы должны использовать один из алгоритмов кратчайшего пути, Dijkstra Shortest Path является наиболее подходящим, поскольку вам нужно найти путь между двумя вершинами. Существует пример для его использования в буст-дистрибутиве. Есть несколько вариантов получения выходных данных из этой функции: либо путем предоставления карты свойств расстояния, либо построения карты предшественника, либо написанием пользовательского посетителя.

Answer 3

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