performance - 住户地址之间的最短距离/路径

Question

如果您想知道两个家庭地址之间的最短距离/路径，您会使用哪种数据结构来有效地返回答案？

假设您正在考虑美国所有家庭的集合(约 1 亿)。

考虑到输入大小如此之大，我正在努力想出一个实用的数据结构。 Dijkstra 的效率似乎太低了，但我猜想有一种方法可以预处理路径以使这样的查询成为可能。我只是不确定从哪里开始。

Answer 1

Dijkstra 的算法或非常相似的东西它可能是基础，尽管你可以期望它是高度优化的。如果您将高权重放在住宅街道上，并随着道路容量的增加而降低权重，那么您会很快缩小搜索空间。

您还可以预期在主要城市之间存在预先计算好的路线。所以如果你在迈阿密并且你想去洛杉矶，大部分路线都是预先计算好的。你只需要弄清楚如何从迈阿密的房子到最近的高速公路交汇处，以及如何从洛杉矶的高速公路到目的地。

考虑到邮政编码的数量少于 100,000，因此拥有一个预先计算出从每个邮政编码到每个其他邮政编码的路由的表并不是不可想象的。我们只谈论 100 亿条路线。天真地存储，这将是相当多的数据，但它是高度可压缩的。例如，考虑一下您的邮政编码数据库是否只包含到最近的主要公路的路线。一旦您走上主要高速公路，数据量就不会那么大了。

尽管所有的道路都是相连的，但您不会将其视为一个巨大的图形。相反，你有一堆更小的图——集群——你计算集群之间的路线。在数据达到可管理的大小之前，您还会有集群中的集群。

至少，这就是我解决问题的方式。