Comments 3
Вам бы специалиста по теории графов в конусльтанты надо, а не новые библиотеки. У вас тут неправильные алгоритмы применяются вообще.
Вам не надо искать все пары расстояний. Вам надо найти центр планарного взвешенного графа же. Для этого в том же networkx есть метод. Это будет сильно быстрее, чем искать все пары расстояний. Если надо не только лучшую точку найти, но и как-то раскрасить все точки на карте для оператора, то можно воспользоваться тем, что у вас граф планарен. Чем ближе к центру графа находится точка, тем лучше она будет. Так что можно взять лишь несколько ближайших точек к центру и для них всех найти расстояния до всех вершин той же Дейкстрой и в зависимости от максимумального раскрасить. Или вообще раскрасить их в зависимости от расстояния до центра (расстояния - по графу, конечно, а не на карте).
И вообще, раз у вас все веса в планарном графе - это просто геометрические расстояния на плоскости, тот тут наверняка есть более специализированные и быстрые алгоритмы.
Добрый день! Спасибо за замечание, но не все так просто, как хотелось бы.
В данном случае фактическое расстояние является лишь одной из фичей, которая используется для расчета оптимальной локации. Согласитесь, что размещать даркстор вот прям-прям в самом центре какого-то района ну уж очень предсказуемо.
В тексте, возле спойлера, где представлен результат расчета для локации из примера, было отмечено, что мы используем еще и "дополнительные показатели для каждой ноды", которые у нас имеются помимо этого самого расстояния.
Скажу больше, что вполне возмозжно и такое, что даркстор может быть расположен и не возле центроида, а где нибудь в уголке, вот такой вот парадокс, все дело в других фичах, но о них мы не расскажем, увы нельзя.
Но один из параметров, судя по ускорению, самый медленный в расчете - это поиск худшего расстояния в графе для каждой вершины и назначение ей какого-то веса в один из параметров. И вот тут как раз можно центроиду дать максимальную оценку в этом параметре, вершинам рядом - чуть поменьше, а всем остальным - ноль. Например. Возможно есть быстрый алгоритм точного рассчета худших расстояний для всех вершин в планарном географическом графе.
Еще чуть-чуть быстрее ищем кратчайший путь на Python