Comments 10
Завтра на Google Developer Day Фицпатрик, наверное, опять будет про социальные графы говорить. Как жаль, что не попаду. Разбередил душу ваш пост :)
Нет, в этот раз Чуи. Или в прошлый тоже он был?
А зачем, простите, «перебирать все возможные пути от пользователя до искомого человека»?
Они про алгоритмы нахождения кратчайшего пути слышали?
120 миллионов ребер — это примерно как все дороги Европы. Можно и не извращаться.
Они про алгоритмы нахождения кратчайшего пути слышали?
120 миллионов ребер — это примерно как все дороги Европы. Можно и не извращаться.
Да, с перебором всех возможных путей я наверное погорячился. И тем не менее основная мысль от этого не меняется — алгоритм поиска кратчайшего пути будет работать значительно быстрее на персональном графе, чем на полном.
Логично.
Забавно, что выборка персонального подграфа и есть нахождение кратчайших путей ко всем вершинам, удаленным на, скажем, 3 ребра от выбранной вершины. По-английски это называется catchment area или coverage area и делается это с помощью того же алгоритма Дейкстры, который останавливается, не когда достиг искомой вершины, а когда путь из каждой анализируемой вершины превышает 3.
Забавно, что выборка персонального подграфа и есть нахождение кратчайших путей ко всем вершинам, удаленным на, скажем, 3 ребра от выбранной вершины. По-английски это называется catchment area или coverage area и делается это с помощью того же алгоритма Дейкстры, который останавливается, не когда достиг искомой вершины, а когда путь из каждой анализируемой вершины превышает 3.
Банальные графы… Pathfinding
Sign up to leave a comment.
Как устроен поиск пути между пользователями в LinkedIn.