У меня похожая задача, только глубина = 2 — habrahabr.ru/qa/42302/
Тоже решал её волнами с двух сторон, кажется, что это единственный разумный вариант. Единственный вопрос, есть ли какие-либо СУБД, которые реализуют этот алгоритм из коробки?
Я действительно не привел граничные условия. Там не так уж много возможных комбинаций, если ограничивать путешествие по глубине. Обновил условие задачи.
Я забыл привести граничные условия организации графа, в связи с этим уточняю вопрос.
У нас есть 2 вида точек: А и В, где Qa/Qb = 1/10, A<-->B. Таким образом точки A связаны друг с другом через ограниченное количество точек B.
Пример графа:
As <--> B1 <--> Ad
B2 <-->
Пример запроса к графу:
Найти все возможные B, которые ведут от As до Ad.
На текущий момент это все успешно работает на MySQL Percona под XtraDB примерно так:
1) Получаем все B, которые имеет As.
2) Получаем все A, которые имеет соответствующие B кроме As.
На мой взгляд тут трудно найти более оптимальный алгоритм. Я ищу инструмент, который может это сделать быстрее, проще и прозрачнее.
Тоже решал её волнами с двух сторон, кажется, что это единственный разумный вариант. Единственный вопрос, есть ли какие-либо СУБД, которые реализуют этот алгоритм из коробки?