真实面经题目 · 原创解析
A* 相比 Dijkstra 优化了什么问题?
A* 主要优化的是 Dijkstra 在单源到单目标最短路径场景中的均匀扩展问题。Dijkstra 只按当前已知代价 g(n) 从近到远扩展,不利用终点方向信息,因此会探索大量与目标无关但距离起点较近的节点。A* 在 g(n) 基础上加入启发式估计 h(n),用 f(n)=g(n)+h(n) 同时衡量已经走了多远和预计还要走多远,从而优先扩展更可能通向目标的节点。
这道题出自阿里巴巴算法工程师面经(面试大师面经题库,2026 年 5 月整理)。