什么是 SPFA 算法？

SPFA（Shortest Path Faster Algorithm）是一种用于计算单源最短路径的算法。与 Dijkstra 算法不同，SPFA 可以处理带有 负权边 的图。它实际上是 Bellman-Ford 算法的一种队列优化版本。

核心思想

SPFA 算法的核心思想是 动态逼近。它维护一个队列，队列中存放着“刚刚被成功松弛过”的顶点。只有当一个顶点的距离 dist[u] 变小时，它才有可能去更新它的邻居 v 的距离 dist[v]。因此，只有那些距离值变小的顶点，才需要被放入队列中，作为下一轮松弛操作的出发点。