我看维基百科的介绍, 加上iceboy某次给我的讲解, 写出来了一个。
SPFA 是一种很简单而且很快的算法用来求单源最短路(就是在一个有向图里面, 从一个点出发, 到达所有点的最短路径)。
需要的数据结构有一个数组和一个存有图的数组的数组(也叫做二维数组)。
数组里面存的是目前的解。
比如有 1 2 3 4 5 五个顶点从 1 出发, 那么数组里是 0 ∞ ∞ ∞ ∞
然后还需要一个队列, 把初始节点1放到队列里, 就可以开始 SPFA 了!
过程是这样的, 每次从队列里取出一个顶点。
然后枚举这个顶点的所有边。
如果能够找到一个更好的解, 就更新那个数组, 同时把被更新的点放到队列里。 //貌似叫做"松弛操作"
如果队列什么都没有了, 说明完成了。
就是这样。
这个题目就是判断有没有负权回路。
判断有没有负权回路只需要判断某点进入队列的次数, 大于n-1就说明存在负权回路。
Read full article from poj 3259 Wormholes/虫洞 SPFA | Wandai Blog
No comments:
Post a Comment