最短路之SPFA

解决存在<<<负环>>>的图的单源最短路径:

判断有无负环:

  如果某个点进入队列的次数超过N次则存在负环(SPFA无法处理带负环的图)

这里,只介绍用bfs(深搜)的SPFA,如果想了解更多,参考http://www.cnblogs.com/scau20110726/archive/2012/11/18/2776124.html

原文地址:https://www.cnblogs.com/ouyang_wsgwz/p/6666218.html