Как найти все пути в графе между двумя узлами до заданного числа промежуточных узлов?

Question

У меня огромный ориентированный граф с около миллиона узлов и более десяти миллионов ребер.Края не взвешены.Граф - это граф, похожий на маленький мир.Фактически я вижу, что каждый узел (в среднем) связан с другим узлом через три промежуточных узла.

Учитывая этот график, вы можете придумать быстрый алгоритм, который возвращает все пути (без циклов) между начальным и конечным узлами, но только до заданного максимального числа N промежуточных узлов (и в моем случае Nбольшую часть времени будет между 0 и 3)?

Answer 1

Если бы ваш график был ненаправленным, вы наверняка захотите выполнить двунаправленный поиск в ширину.Для путей длины 2 перечислите ребра от начального узла и конечного узла и посмотрите, где они пересекаются.Для путей длиной 3 перейдите на 2 глубины от конечной точки с меньшей степенью и на одну глубину на узле с большей степенью.

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

Answer 2

Возможно, сначала дыхание с обеих сторон одновременно?Возьмите соседей A и соседей B. Если вы еще не нашли ссылку, добавьте A к «соседям a» и B к «соседям B», затем найдите любую связь между двумя наборами.

Чтобы расширить его немного больше, чем на три ссылки, списки «соседей A / B» должны содержать немного больше.Вы не сможете сделать это в памяти - вам понадобится таблица с параметрами

whatever TRANSACTION_ID; (or use an ORACLE 1-per-session temp table)
boolean MY_BFS_WAS_ROOTED_AT_A;
int NODE_ID;
int previous_node_id;

(вам не нужно отслеживать глубину, если вы проверяете петли в своем операторе вставки)

вы нашли путь, когда существует какой-либо

select from pathfinder a, pathfinder b
where a.taxn_id = foo and b.tnx_id=foo
and a.MY_BFS_WAS_ROOTED_AT_A = false
and b.MY_BFS_WAS_ROOTED_AT_A = true
and a.node_id = b.node_id

Не забудьте очистить таблицу, когда вы закончите!Выполнение всего одной транзакции и откат назад может быть самым простым способом.