ttas
@ttas

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

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


Так же, буду благодарен ссылке, так как уже выбился из сил искать толковую информацию по графам. Спасибо.
  • Вопрос задан
  • 3542 просмотра
Решения вопроса 1
TheHorse
@TheHorse
Поиск в глубину с ограничением глубины = 4.
Дойдя до глубины = 4 добаляете в отсортированый список. Все ж просто?
Ответ написан
Пригласить эксперта
Ответы на вопрос 2
3d6
@3d6
Если все симметрично, то наиболее разумный вариант — поиск в ширину (это то, что называют волной) с 2х сторон, по 2 шага с каждой. Итого будет два списка по 100^2 вершин, в котором нужно найти пересечения, и их отсортировать. С учетом того, что полученных путей почти всегда будет менее 10000, то наверное нет смысла париться, можно смело запихнуть все в кучу и пройтись быстрой сортировкой (хотя зависит от системы, если это место будет занимать значительную часть ресурсов — то наверняка можно придумать что получше).

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

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы
DDoS-GUARD Ростов-на-Дону
от 70 000 до 120 000 ₽
OZON Москва
от 180 000 до 270 000 ₽
Softaria Новосибирск
от 100 000 до 150 000 ₽
18 апр. 2021, в 16:33
400 руб./за проект
18 апр. 2021, в 16:28
3000 руб./за проект