SPFA算法在使用队列与栈时取决于具体应用场景与图结构特性其核心区别在于节点扩展顺序对松弛效率的影响。‌使用队列标准实现‌采用先进先出FIFO策略模拟广度优先搜索BFS按层次逐步松弛节点。适用于‌通用场景‌尤其在‌稀疏图‌中表现稳定平均时间复杂度接近 O(kE)O(kE)kk 为平均入队次数。队列能均衡地传播最短路径更新避免局部深度搜索导致的冗余是‌工程实现的首选‌适合大多数算法竞赛与实际系统。‌使用栈优化变体‌采用后进先出LIFO策略模拟深度优先搜索DFS优先深入最新更新的路径。在‌特定图结构‌如链状、树状或具有强深度依赖的图中栈能更快触发负环检测或加速收敛。例如在 POJ3159《Candies》等卡时间的竞赛题中‌栈版本常能通过队列超时的数据‌。但其最坏时间复杂度仍为 O(VE)O(VE)且稳定性差可能在随机图中性能劣化。表格使用场景推荐结构原因通用单源最短路含负权队列稳定、均衡、兼容性好图呈链式或深度优先结构栈深度优先加速路径传播需快速检测负环栈DFS 更易重复访问同一节点数据卡队列超时栈竞赛中常用“换栈过题”技巧稠密图或无负权避免SPFA直接使用 Dijkstra 更优注栈优化并非理论创新而是工程层面的启发式调整。其有效性高度依赖输入数据分布‌不建议作为默认实现‌。