最短路径算法:Dijkstra 的原理与实现
哪些公司问过
答案要点
- Dijkstra 适用于非负权单源最短路,基于贪心,每次确定距离最小的未确定节点
- 用邻接表建图,小顶堆维护候选节点,弹出后松弛所有出边
- 堆中旧记录用懒删除:弹出距离大于 dist 时跳过;堆优化复杂度 O((V+E) log V)
- LC743 取所有节点最短距离的最大值,存在不可达节点返回 -1
- 负权用 Bellman-Ford(可检测负环),全源用 Floyd,无权图用 BFS
易错点
- 在有负权边的图上使用 Dijkstra
- 忘记懒删除判断,重复处理已确定的节点,导致超时
- LC743 中没有检查不可达节点,直接返回最大值
面试官常见追问
- 为什么 Dijkstra 不能处理负权边?
- 怎么输出具体路径?
- 稠密图上用不用堆?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。