Posted on 2010-08-19 11:58
acronix 阅读(1866)
评论(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)