Posted on 2010-08-19 11:58
acronix 阅读(1876)
评论(0) 编辑 收藏 引用 所属分类:
hzshuai解题中算法总结
spfa是使用队列进行渐近求最短路的方法：
思想为：
1、只保存被更新但未扩展的节点（即未进队的节点）
做法：
1、n建立一个队列，初始时队列里只有起始点，在建立一个表格记录起始点到所有点的最短路径（该表格的初始值要赋为极大值，该点到他本身的路径赋为0）。然后执行松弛操作，用队列里有的点去刷新起始点到所有点的最短路，如果刷新成功且被刷新点不在队列中则把该点加入到队列最后。重复执行直到队列为空
2、n期望的时间复杂度O(ke)， 其中k为所有顶点进队的平均次数，可以证明k一般小于等于2。
使用队列的伪代码：
queue <Node *> Q;
while(!Q.empty()) Q.pop();
memset(visit , 0 , sizeof(visit));
for(i = 2;i <= p; ++ i) dist[i] = inf;
dist[1] = 0;
Q.push(father[1]);
visit[1] = true;
练练手：HDU 3499
用队列如何判断负环呢？当某个节点n次进入队列，则存在负环，此时时间复杂度为O(n*m),n为节点，m为边，
当n= 1000000 m=2000000是，那时间就相当可观了。
有什么更好的方法吗？有！深度优先搜索，得到一个更新的节点接扩展，
然后利用栈，当出现栈中的节点时，则存在负环。时间复杂度就基本保持在O(m)内；
实战 WordRings(ACM-ICPC Centrual European 2005)