Сложные сети - поиск всех возможных кратчайших путей между парой узлов

Question

У меня есть база данных, которая описывает огромную сеть. Он состоит из около 18000 вершин. Теперь мне нужно найти все возможные кратчайшие пути между парой узлов. Я попытался реализовать итеративную DFS, но проблема заключается в экспоненциальном росте. Необходимое количество времени становится огромным, поскольку вершины имеют высокую степень превышения. Можете ли вы предложить какой-то алгоритм, который будет работать быстрее. Сложная сеть, которая у меня есть, направлена ​​и взвешена. Любые предложения будут очень полезны.

Спасибо, экта

Answer 1

Для взвешенного графа с положительными весами обычно используется поиск с равномерной стоимостью, известный как алгоритм Дейкстры. Другие алгоритмы могут быть быстрее в определенных случаях. Например, если ваши данные позволяют вам определить эвристическую функцию, вы можете использовать вместо нее A *. Или, если ваша сеть не масштабируется (то есть ее степень распределена по степенному закону), вы можете использовать вариант алгоритма Дейкстры, описанный в Peng et al. 12.

Есть также несколько связанных с этим вопросов SO, на которые вы, возможно, захотите взглянуть, например, есть ли лучший способ, чем алгоритм Дейкстры, найти быстрый путь, который не превышает указанную стоимость, или Есть более быстрые алгоритмы, чем Дейкстра?,

РЕДАКТИРОВАТЬ: чтобы найти все кратчайшие пути между данной парой узлов, вы все равно можете использовать Dijkstra, с некоторыми изменениями:

• Используйте дерево поиска, чтобы применить алгоритм (в отличие от применения алгоритма, основанного непосредственно на исследуемом графике). Таким образом, вы можете легко представить несколько путей, ведущих к одному и тому же узлу. См. Статью поиска WP Breadth-first, чтобы увидеть пример дерева поиска. Так что это больше вопрос структуры данных.
• Разрешить повторное посещение уже посещенного узла, при условии, что 1) путь, ведущий к этому узлу, отличается от пути, уже представленного в дереве, и 2) не длиннее этого существующего пути. С точки зрения дерева поиска, это означает, что один граф-узел можно представить в виде двух разных узлов дерева, каждый в другой ветви.
• Развивайте дерево до тех пор, пока не найдете первое оптимальное решение, затем продолжайте разрабатывать дерево, используя длину этого решения в качестве предела (т.е. вы прекращаете разработку ветви, когда она достигает этой длины).
• В конце каждая ветвь, содержащая целевой узел, должна соответствовать оптимальному кратчайшему пути.

Вы также можете взглянуть на этот вопрос (хотя он касается невзвешенных графов): поиск всех кратчайших путей между двумя узлами в невзвешенном неориентированном графе