ускорение алгоритма поиска кратчайшего пути

Question

Добрый день, дорогие друзья.

Я хочу найти кратчайший путь в случайном графе. Я использую библиотеку ускорителей. Насколько я понимаю, мне нужно построить график, используя существующие расстояния между точками. После этого мне нужно использовать некоторый алгоритм ...

Как я вижу, алгоритм Дейкстры действительно находит все пути от 1 точки до других. (Это должно быть медленным?)

A * хотят некоторые дополнительные данные (не только расстояние)

Как я могу найти кратчайший путь между 2 точками? Я видел много кратчайших заголовков алгоритмов в папке bgl, но я не нашел примеров, как их использовать.

Также я могу предкомпромировать что-то для графика.

Что мне делать?

Answer 1

это зависит от того, сколько узлов у вас есть, как вы упомянули ваши узлы вокруг O (10^4) и ребра O (10^4), который хорошо
так в BOOST LIBRARY DOCS его Сасах Сложность времени O (V log V + E)., так что если вы положите V = 10^4 и E = 10^4, вы получите около O (10^5), что очень хорошо и может работать менее 1 секунды на обычном компьютере, чтобы вы могли его использовать.

A * Алгоритм может работать быстрее, чем A *, но она нуждается в эвристической функции, которая должна быть монотонной и допустимы и это может быть трудно найти, что функция в зависимости от вашей проблемы.

поэтому я думаю, что Dijkstra будет достаточно хорош для вашего дела

Answer 2

Алгоритм Дейкстры принимает O (E log (n)) время - где E = #edges и N = # узлов. Должно быть достаточно быстро. Просьба прокомментировать приблизительные значения E и N.

В некоторых случаях (например, социальный график) следующее: - при условии, что вес ребер 1, N очень большой, степень узлов небольшая (несколько сотен): Сделайте 2 уровня BFS из node1, 2 уровня BFS из узла2 и пересечь множества. Если длина пути < = 4, вы найдете его.