随笔-20  评论-16  文章-36  trackbacks-0

算法简介 
         SPFA(Shortest Path Faster Algorithm)是Bellman-Ford算法的一种优化,减少了不必要的冗余计算。 它可以在O(kE)的时间复杂度内求出源点到其他所有点的最短路径,可以处理负边,但判断负回路不方便。
         值得注意的是,得到可行解后,可以看成新的约束:xi-xj<=d[i]-d[j],即d[i]为xi-x0的最大值。由此可以看出,SPFA和Bellman-Ford算法解决差分约束系统问题时,实际上是把约束条件强化了,使得满足任意约束条件的值都能构造出一个完整的解。同样的,当约束方程为>=时,求出的xi-xj>=d[i]-d[j],故d[i]为xi-x0的最小值。理解后灵活运用,差分约束问题就比较容易解决了。(这里设x0为源点)
      
算法流程 
         SPFA对Bellman-Ford算法优化的关键之处在于意识到:只有那些在前一遍松弛中改变了距离估计值的点,才可能引起他们的邻接点的距离估计值的改变。因此,算法大致流程是用堆栈或队列存放被成功松弛的顶点。初始时,源点s入队。当队列不为空时,取出栈顶/队首顶点,对它的邻接点进行松弛。如果某个邻接点松弛成功,且该邻接点不在堆栈/队列中,则将其入栈/队。经过有限次的松弛操作后,堆栈/队列将为空,算法结束。

int N,M;    //实际的顶点数和边数
struct Edge{
    
int to, cost;
    Edge
* next;
}
edges[MAXM+1];        //MAXM为最大边数
Edge* linklist[MAXN+1]={0};        //MAXN为最大顶点数
void SPFA( Edge* linklist[], int dist[], int source ){    //参数分别为边的临接表、距离、源点,堆栈实现
    bool bInQ[MAXN+1]={0};        //判断点是否在堆栈中
    int stack[MAXN+1]={0}, top=0;    //保存活动结点
    forint i= 1; i<= N; i++ )
        dist[i]
= INF;
    dist[source]
= 0;
    stack[top
++]= source;
    
while( top ){
        
int cur= stack[--top];
        Edge
* q= linklist[cur];
        bInQ[cur]
= 0;
        
while( q ){
            
if( dist[q->to]> dist[cur]+q->cost ){
                dist[q
->to]= dist[cur]+q->cost;
                
if!bInQ[q->to] )
                    stack[top
++]= q->to;
                bInQ[q
->to]=1;
            }

            q
=q->next;
        }

    }

}

posted on 2009-04-23 19:50 古月残辉 阅读(1985) 评论(0)  编辑 收藏 引用 所属分类: Template

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