图论算法总结:单源最短路(Dijkstra 与 SPFA)
综述由AI生成图论单源最短路算法主要包括 Dijkstra 和 SPFA。Dijkstra 适用于边权非负图,利用贪心策略结合优先队列优化,时间复杂度为 O((m+n)logn)。SPFA 作为 Bellman-Ford 的队列优化版本,支持负权边并能检测负环,但在特定数据下可能退化为 O(mn)。文章详细阐述了两种算法的核心思想、代码实现及适用场景,强调 Dijkstra 在常规最短路问题中的稳定性以及 SPFA 在负环判断中的必要性。













