Хоть 600

Но это 200к в кубе вершин.

Интересно, сколько это займёт.

На одном потоке же.

Да, но дейкстра тоже не линейно скейлится и при этом у него сопутствующие расходы нифига не маленькие.

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

Добавлю это как коммент к коду.

Просто если ты можешь на РФ рассчитать тыщу точек так быстро, то может тут все вообще изначально абсолютно похерено .

И надо просто препроцессинг графа перевести на рельсы этого подхода.

А дальше жизнь станет гораздо проще.

Владимир Высоцкий. Вершина

Оно всё равно не заточено под задачу посчитать расстояния между вообще всеми вершинами.

Для такого лучше взять специализированные алгоритмы.

А тому же того же Флойда уоршелла можно на кластере запустить, в отличие от альтернатив https://arxiv.org/abs/1902.04446

Окей, это принято. Но если чуть отойти от спецификации и чуть здоровее посмотреть, то в итоге-то надо знать сколько водителю до пассажира реально нужно проехать, так как цель этого с точки зрения бизнеса это в первую очередь расход бензина. Водители уходят, если маршрут нечестный, особенно сейчас, по крайней мере так говорят бизнес-аналитики. Эти опенсоурсные роутеры такую задачу же по ступ и решают? Специфика в том, что водитель от пассажира может быть сколько угодно далеко.

И запросов на маршрутизацию до тысячи в секунду на продакшин кластер.

Ну а если вам хватит ресурсов, чтобы посчитать Флойда уоршелла для нужного вам графа, то остальное дело техники.

Можно банально эту матрицу держать в памяти и быстрее этого уже ничего не будет

Проблемы у вас возникнут, только если захочется масштабироваться сильно

Но тогда в любом случае от подхода с расчетом всех расстояний между всеми вершинами придется отойти

Пока такой задачи не стоит.