# Google Maps is unreasonably fast. Let me explain

- Channel: [Veritasium](https://www.youtube.com/channel/UCHnyfMqiRRG1u-2MsSQLbXA)
- Published: 2026-05-30
- Source video: [Watch on YouTube](https://youtube.com/watch?v=kS-CGkiPetQ)
- Read on ReadTube: https://www.read.tube/p/videos/kS-CGkiPetQ
- Language: Simplified Chinese

## Summary

**谷歌地图为何如此之快**

谷歌地图之所以能迅速给出路线，核心在于它不是单纯暴力搜索所有可能路径，而是不断演化出更聪明的最短路算法。视频从迪杰斯特拉算法讲起，再到启发式搜索、双向搜索和分层预处理，最后解释了接近毫秒级查询速度的来源。

视频先说明了最短路径问题为何在现实中极其庞大：道路网络的路线组合数量近乎天文数字，直接穷举根本不可能。迪杰斯特拉算法通过按“当前最小代价”扩展节点，保证找到最短路，但在大规模路网中仍会探索大量无关区域，因此在北美级别的路网上查询仍然偏慢。

随后视频展示了几种加速思路：A* 利用到目标的直线距离作为启发式，优先朝目标方向搜索，能显著缩小搜索空间；双向搜索从起点和终点同时展开，也能减少需要检查的节点。不过，这些方法仍然没有充分利用道路网络天然存在的层级结构，比如小路、主干道和高速公路之间的差别。

真正把查询速度推到极快水平的是基于层级和预处理的方案，尤其是自适应收缩层级。它先通过嵌套分割自动找出“重要节点”，再在收缩节点时添加捷径，确保不会漏掉经过低等级道路的最短路。这样做的代价是前期预处理较重，但换来的是查询阶段只需搜索极少节点，实验中可把数秒级的迪杰斯特拉搜索压到约二百微秒。

- 迪杰斯特拉算法奠定了现代路径规划的基础，但在超大路网中仍会搜索过多节点。
- A* 通过启发式把搜索导向目标，适合距离最短或游戏寻路等场景。
- 双向搜索能把搜索范围从两端同时压缩，但仍不理解道路层级。
- 手工分层曾用于早期导航系统，但难以自动化、也难以保证最优性。
- 嵌套分割和收缩层级通过自动排序节点、添加捷径，把层级信息编码进图中。
- 自适应收缩层级把“重预处理、超快查询”这条路线做到了工程上可用的极致。
- 视频最后强调，许多现代最短路方法本质上仍建立在迪杰斯特拉思想之上，体现了简单算法的长期生命力。
