posts - 64, comments - 4, trackbacks - 0, articles - 0

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)

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理