SPFA算法模板

求单源最短路的SPFA算法的全称是：ShortestPathFasterAlgorithm。SPFA算法是西南交通大学段凡丁于1994年发表的.从名字我们就可以看出，这种算法在效率上一定有过人之处。很多时候，给定的图存在负权边，这时类似Dijkstra等算法便没有了用武之地，而Bellman-Ford算法的复杂度又过高，SPFA算法便派上用场了。