图的最短路径算法思路(BFS/Dijkstra 等)
哪些公司问过
答案要点
- BFS:无权图单源最短路,O(V+E);0-1 权图用双端队列 BFS
- Dijkstra:非负权,优先队列贪心取最小距离点并松弛,O((V+E) log V)
- Bellman-Ford:可处理负权,V−1 轮松弛,O(VE),可检测负环;SPFA 为队列优化
- Floyd:多源最短路,动态规划三重循环,O(V³),适合稠密小图
- 输出路径:记录前驱节点,从终点回溯
易错点
- 在负权图上使用 Dijkstra
- Floyd 把中转点 k 放在内层循环
- BFS 求带权图最短路
面试官常见追问
- Dijkstra 为什么不能处理负权边?
- A* 和 Dijkstra 有什么关系?
- Floyd 的循环顺序有什么讲究?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。