面试题库 › Java 后端 › 最短路径算法:Dijkstra 的原理与实现

最短路径算法:Dijkstra 的原理与实现

难度 ★★☆在 4 场真实面经中被问到 方向:Java 后端考点:图论

哪些公司问过

腾讯1华为1蚂蚁集团1英雄互娱1

常见岗位:Java 后端、iOS、C/C++ 软件开发

答案要点

  1. Dijkstra 适用于非负权单源最短路,基于贪心,每次确定距离最小的未确定节点
  2. 用邻接表建图,小顶堆维护候选节点,弹出后松弛所有出边
  3. 堆中旧记录用懒删除:弹出距离大于 dist 时跳过;堆优化复杂度 O((V+E) log V)
  4. LC743 取所有节点最短距离的最大值,存在不可达节点返回 -1
  5. 负权用 Bellman-Ford(可检测负环),全源用 Floyd,无权图用 BFS

易错点

面试官常见追问

完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。

相关面试题