Aлгоритм нахождения подграфов?

Question

[ttas]

Существует неориентированный граф на миллион вершин и 100 миллионов ребер. У каждого ребра есть свой вес. Задача следующая. Заданы две вершины. Необходимо найти все пути между двумя вершинами, состоящие из 4 ребер, причем пути должны быть отсортированы в порядке увеличения/уменьшения общего веса пути.


Так же, буду благодарен ссылке, так как уже выбился из сил искать толковую информацию по графам. Спасибо.

Comments

[Limosha]

Скорость/память важна?

[ttas]

Конечно, это очень важный момент. Иначе я бы пошел в лоб: перебором с двух сторон.

Answer 1

[TheHorse]

Поиск в глубину с ограничением глубины = 4.
Дойдя до глубины = 4 добаляете в отсортированый список. Все ж просто?

Comments

[TheHorse]

И если граф в нормальном виде — количество итераций около 100^4 = 100 000 00 — может за 1 сек справится.

Answer 2

[3d6]

Если все симметрично, то наиболее разумный вариант — поиск в ширину (это то, что называют волной) с 2х сторон, по 2 шага с каждой. Итого будет два списка по 100^2 вершин, в котором нужно найти пересечения, и их отсортировать. С учетом того, что полученных путей почти всегда будет менее 10000, то наверное нет смысла париться, можно смело запихнуть все в кучу и пройтись быстрой сортировкой (хотя зависит от системы, если это место будет занимать значительную часть ресурсов — то наверняка можно придумать что получше).

И — такой вариант примерно в 100^2 / 2 раз быстрее поиска из одной вершины. Чуть-чуть не подумав, вычислительно простую задачу можно легко превратить в ресурсоемкого монстра :)

Comments

[rmk]

У меня похожая задача, только глубина = 2 — habrahabr.ru/qa/42302/
Тоже решал её волнами с двух сторон, кажется, что это единственный разумный вариант. Единственный вопрос, есть ли какие-либо СУБД, которые реализуют этот алгоритм из коробки?

Answer 3

[Velitsky]

В принципе, TheHorse, всё правильно сказал. Правда, с точки зрения терминологии, правильнее сказать (ИМХО) что надо реализовать алгоритм фронта волны от одной точки к другой, хотя по сути это одно и то же. Правда немного опечатался с цифрами: 100^4= 100 000 000.

Comments

[ttas]

То есть, вы имеете в виду, опять же, простой перебор с исходной вершины до требуемой? Вчера ложился спать, почему-то показалось, что более оправданной будет запустить две такие волны с обеих вершин навстречу. Или я не прав?