一个城市路网约 10^8 个节点、2.5×10^8 条边，边权是通行时间（非负，但按早晚高峰每 5 分钟整体更新一次）。要支持单点到单点最短路查询、峰值 10^4 QPS、P99 延迟 < 50ms。朴素 Dijkstra 单次查询要扫描大量节点。你怎么选算法与架构？说清预处理成本、查询延迟、以及权重频繁变化带来的矛盾怎么权衡。

面试官在考什么

考察在“图规模 + 高 QPS + 动态权重”三重约束下做算法选型与架构权衡，而不是复述 Dijkstra 流程。

最短路

回答框架 · 前两步

1. 朴素 Dijkstra 单次约 O((V+E)logV)，在这个规模下要扫近全图，10^4 QPS 完全不可行。
2. 路网稀疏且近似平面图，适合预处理加速：Contraction Hierarchies 或 A* + 地标（ALT），预处理一次分钟到小时级，把查询压到亚毫秒到毫秒级。

延伸阅读

• 避坑与冲刺：简历自洽、六种扣分话术、D-7 准备表

想看这个方向的整体准备路线？ 进入「数据结构与算法」方向页

同一能力域的其他题

• 一个 N×N 的 0/1 网格，N=2000（共 400 万格），0 表示可通行，1 表示障碍，允许上下左右四方向移动，每走一格算 1 步。要求从 (0,0) 走到 (N-1,N-1)，给出最短步数，不可达返回 -1。内存上限 256MB。请说明你选 BFS 还是 DFS、队列和 visited 怎么设计、以及 visited 具体在什么时刻打标记。
• 社交关系图共 10^9 个用户，平均出度 200，边存放在分布式 KV 上（一次邻居查询约 5ms），单机可用内存 64GB。现在要找出指定用户 A 的 3 度以内（含 3 度）的全部用户 ID。你选 BFS 还是 DFS？写出你的遍历控制逻辑，估算 frontier（当前层待扩展集合）的最大规模，并说明用什么结构做去重。
• 你接手一个权限可达性服务：授权图约 500 万节点、2000 万条有向边（用户→角色→权限组→资源），业务上允许成环。线上要回答『用户 u 能否到达资源 r』，峰值 10 万 QPS、P99 要求 20ms。上一版实现是每次请求从 u 出发做一次 DFS，线上大面积超时并偶发栈溢出。请给出你的方案、演进路径和取舍。
• 给你一个 1000×1000 的 0/1 网格（1 是陆地，0 是水），上下左右相邻的陆地属于同一个岛，要求返回岛屿数量。A 同学用递归 DFS 做 flood fill，样例全过，但把规模放大到接近满屏陆地时程序崩溃。请说明崩溃的原因，写出你会怎么改；并说明同一份数据用 BFS 写时，队列规模的最坏情况是什么量级。
• 有向图有 4 个节点 s、a、b、t，边和权值是：s→a = 1，s→b = 2，b→a = -2，a→t = 3，b→t = 10。用朴素 Dijkstra（每次从未确定的节点里取 dist 最小的那个标记为已确定，之后不再更新它的 dist）从 s 求到 t 的最短路。请说出它算出的 dist[t] 是多少、正确答案是多少、差在哪一步上，然后说明什么样的图 Dijkstra 才是安全的。
• 你负责一个路径规划服务：路网约 50 万节点、150 万条有向边，边权是通行时长且随早晚高峰变化，线上 2000 QPS，要在 50ms 内返回最快路径。当前实现是每个请求跑一次 Dijkstra。请说明你会怎么演进这个系统，以及每一步的代价。