首页 > 代码库 > SPFA算法 O(kE)
SPFA算法 O(kE)
主要思想是：
初始时将起点加入队列。每次从队列中取出一个元素，并对所有与它相邻的点进行修改，若某个相邻的点修改成功，则将其入队。直到队列为空时算法结束。
这个算法，简单的说就是队列优化的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> 6 using namespace std; 7 const int maxn=0x7f; 8 bool vis[1001]; 9 int map[1001][1001],dis[1001],queue[1001],path[1001];10 int n,m,head=0,tail=1,now;11 12 13 void spfa(int x)14 {15 queue[head]=x;16 vis[x]=true;17 dis[x]=0;18 path[x]=x;19 while(head<tail)20 {21 now=queue[head];22 for(int i=1;i<=n;i++)23 {24 if(dis[i]>dis[now]+map[now][i])25 {26 dis[i]=dis[now]+map[now][i];27 path[i]=now;28 if(vis[i]==false)29 {30 queue[tail++]=i;31 vis[i]=true;32 }33 }34 }35 vis[now]=false;36 head++;37 }38 }39 void print(int st,int en)40 {41 int q[1001];42 int tot=1;43 q[tot]=en;44 tot++;45 int temp=path[en];46 while(temp!=st)47 {48 q[tot]=temp;49 tot++;50 temp=path[temp];51 }52 q[tot]=st;53 for(int i=tot;i>=1;i--)54 {55 if(i!=1)56 printf("%d -- >",q[i]);57 else58 printf("%d",q[i]);59 }60 cout<<endl;61 }62 int main()63 {64 memset(map,maxn,sizeof(map));65 scanf("%d%d",&n,&m);66 int he,ta,len;67 for(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));75 int start,end;76 scanf("%d%d",&start,&end);77 spfa(start);78 printf("%d\n",dis[end]);79 print(start,end);80 return 0;81 }
SPFA算法 O(kE)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。