首页 / 算法 / SPFA算法 O(kE)

SPFA算法 O(kE)

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了SPFA算法 O(kE)，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2250字，纯文字阅读大概需要4分钟。

内容图文

主要思想是：

    初始时将起点加入队列。每次从队列中取出一个元素，并对所有与它相邻的点进行修改，若某个相邻的点修改成功，则将其入队。直到队列为空时算法结束。
    这个算法，简单的说就是队列优化的bellman-ford，利用了每个点不会更新次数太多的特点发明的此算法。
SPFA 在形式上和广度优先搜索非常类似，不同的是广度优先搜索中一个点出了队列就不可能重新进入队列，但是SPFA中一个点可能在出队列之后再次被放入队列，也就是说一个点修改过其它的点之后，过了一段时间可能会获得更短的路径，于是再次用来修改其它的点，这样反复进行下去。
算法时间复杂度：O(kE)，E是边数。K是常数，平均值为2。
算法实现：
    dis[i]记录从起点s到i的最短路径，w[i][j]记录连接i，j的边的长度。pre[v]记录前趋。
    team[1..n]为队列，头指针head，尾指针tail。
    布尔数组exist[1..n]记录一个点是否现在存在在队列中。
    初始化：d[s]=0,d[v]=∞（v≠s），memset(exist,false,sizeof(exist));
    起点入队team[1]=s; head=0; tail=1;exist[s]=true;
    do
    {1、头指针向下移一位，取出指向的点u。
    2、exist[u]=false;已被取出了队列
    3、for与u相连的所有点v  //注意不要去枚举所有点，用数组模拟邻接表存储
       if (d[v]>d[u]+w[u][v])
         {   d[v]=d[u]+w[u][v];
             pre[v]=u;
             if (!exist[v]) //队列中不存在v点，v入队。
               {         //尾指针下移一位，v入队;
                    exist[v]=true;
                 }
          ｝
    }
    while (head < tail);
循环队列：
　　采用循环队列能够降低队列大小，队列长度只需开到2*n+5即可。例题中的参考程序使用了循环队列。
完整代码： 
                             1
                            //
                            spfa
                             2
                             3 #include<iostream>
 4 #include<cstdio> 
 5 #include<cstring>
 6usingnamespace std;
 7constint maxn=0x7f;
 8bool vis[1001];
 9int map[1001][1001],dis[1001],queue[1001],path[1001];
10int n,m,head=0,tail=1,now;
111213void spfa(int x)
14{
15     queue[head]=x;
16     vis[x]=true;
17     dis[x]=0;
18     path[x]=x;
19while(head<tail)
20    {
21         now=queue[head];
22for(int i=1;i<=n;i++)
23        {
24if(dis[i]>dis[now]+map[now][i])
25            {
26                 dis[i]=dis[now]+map[now][i];
27                 path[i]=now;
28if(vis[i]==false)
29                {
30                     queue[tail++]=i;
31                     vis[i]=true;
32                }
33            }
34        }
35     vis[now]=false;
36     head++;
37    }
38}
39void print(int st,int en)
40{
41int q[1001];
42int tot=1;
43     q[tot]=en;
44     tot++;
45int temp=path[en];
46while(temp!=st)
47    {
48         q[tot]=temp;
49         tot++;
50         temp=path[temp];
51    }
52     q[tot]=st;
53for(int i=tot;i>=1;i--)
54    {
55if(i!=1)
56           printf("%d -- >",q[i]);
57else58           printf("%d",q[i]);
59    }
60     cout<<endl;
61}
62int main()
63{
64     memset(map,maxn,sizeof(map));
65     scanf("%d%d",&n,&m);
66int he,ta,len;
67for(int i=1;i<=m;i++)
68    {
69         cin>>he>>ta>>len;
70         map[he][ta]=map[ta][he]=len;
71    }
72     memset(dis,maxn,sizeof(dis));
73     memset(vis,false,sizeof(vis));
74     memset(queue,0,sizeof(queue));
75int start,end;
76     scanf("%d%d",&start,&end);
77    spfa(start);
78     printf("%d\n",dis[end]);
79    print(start,end);
80return0;
81 }

 

原文：http://www.cnblogs.com/sssy/p/6689553.html

内容总结

以上是互联网集市为您收集整理的SPFA算法 O(kE)全部内容，希望文章能够帮你解决SPFA算法 O(kE)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/1051763.html

来源：【匿名】