Я использую boost::graph и его реализацию Dijkstra.
Я хочу вычислить кратчайший путь из набора вершин в другой набор вершин.Я не хочу вычислять все возможные пути между этими наборами.
Идея заключается в следующем: я нахожусь в здании с входами на разных улицах.Так что я могу начать свое путешествие по любой из этих улиц.Но меня интересует только самый короткий.
Если бы я использовал свою собственную реализацию алгоритма Дейкстры, я бы сделал следующее:
- Для каждого начального узла,карта расстояний до 0
- Добавьте начальный узел в очередь приоритетов.
Хотя установить карту расстояний на 0 с помощью boost::dijkstra_shortest_paths_no_init легко, я не могу понять, как добавитьузел в очереди приоритетов.Я посмотрел на исходный код, и он кажется почти невозможным.Поэтому я подумываю определить свой собственный функтор Combine, который будет возвращать расстояние 0, если я достигну одного из начальных узлов, но это выглядит довольно уродливо.
Я мог бы создать виртуальный узел и добавить ребра извиртуальный узел для начальных узлов.Однако это вызывает некоторые проблемы с одновременным доступом, которых я бы хотел избежать.
Я пропустил возможность в библиотеке boost или кто-то знает об умном обходном пути.Я также подумываю о том, чтобы исправить буст, чтобы разрешить пользовательскую инициализацию очереди с приоритетами.