为生存而奔跑

   :: 首页 :: 联系 :: 聚合  :: 管理
  271 Posts :: 0 Stories :: 58 Comments :: 0 Trackbacks

留言簿(5)

我参与的团队

搜索

  •  

积分与排名

  • 积分 - 268665
  • 排名 - 83

最新评论

阅读排行榜

评论排行榜

SPFA即shotest path faster algorithm,由意思就可以看出该算法效率比较高。

其实SPFA就是bellman-ford算法的一个优化。

具体做法是用一个队列保存待松弛的点,然后对于每个出队的点依次遍历每个与他有边相邻的点(用邻接表效率较高),如果该点可以松弛并且队列中没有该点则将它加入队列中,如此迭代直到队列为空。

据说平均效率是O(E),可见对边稀疏的图用此算法效果是相当可观的。

 

若要判负环路,则记录一个点的入队次数,若超过边数,则有负权环。

#include <iostream>
#include 
<queue>
using namespace std;

const long MAXN=10000;
const long lmax=0x7FFFFFFF;

typedef 
struct  
{
    
long v;
    
long next;
    
long cost;
}Edge;


Edge e[MAXN];
long p[MAXN];
long Dis[MAXN];
bool vist[MAXN];

queue
<long> q;

long m,n;//点,边
void init()
{
    
long i;
    
long eid=0;

    memset(vist,
0,sizeof(vist));
    memset(p,
-1,sizeof(p));
    fill(Dis,Dis
+MAXN,lmax);

    
while (!q.empty())
    {
        q.pop();
    }

    
for (i=0;i<n;++i)
    {
        
long from,to,cost;
        scanf(
"%ld %ld %ld",&from,&to,&cost);

        e[eid].next
=p[from];
        e[eid].v
=to;
        e[eid].cost
=cost;
        p[from]
=eid++;

        
//以下适用于无向图
        swap(from,to);
        
        e[eid].next
=p[from];
        e[eid].v
=to;
        e[eid].cost
=cost;
        p[from]
=eid++;

    }
}

void print(long End)
{
    
//若为lmax 则不可达
    printf("%ld\n",Dis[End]);    
}

void SPF()
{

    init();

    
long Start,End;
    scanf(
"%ld %ld",&Start,&End);
    Dis[Start]
=0;
    vist[Start]
=true;
    q.push(Start);

    
while (!q.empty())
    {
        
long t=q.front();
        q.pop();
        vist[t]
=false;
        
long j;
        
for (j=p[t];j!=-1;j=e[j].next)
        {
            
long w=e[j].cost;
            
if (w+Dis[t]<Dis[e[j].v])
            {
                Dis[e[j].v]
=w+Dis[t];
                
if (!vist[e[j].v])
                {
                    vist[e[j].v]
=true;
                    q.push(e[j].v);
                }
            }
        }
    }

    print(End);

}

int main()
{
    
while (scanf("%ld %ld",&m,&n)!=EOF)
    {
        SPF();
    }
    
return 0;
}
posted on 2009-09-08 16:33 baby-fly 阅读(487) 评论(0)  编辑 收藏 引用 所属分类: Algorithm

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理