首页 > 代码库 > 图论-单源最短路-SPFA算法
图论-单源最短路-SPFA算法
有关概念：
最短路问题：若在图中的每一条边都有对应的权值，求从一点到另一点之间权值和最小的路径
SPFA算法的功能是求固定起点到图中其余各点的的最短路（单源最短路径）
约定：图中不存在负权环，用邻接表存储有向图，di存放从起点到结点i的最短路，q为队列，保存待处理节点
思路：
首先指定起点入队，取当前队头结点u，沿每一条与u相连的边向外扩展，对该边所指向的结点v松弛（比较当前dv与当前du加此边长，更新最短路值dv，以及最短路径prev）如果v不在队列中且更新了最短路值，v进队，直至队列中没有元素时终止
较于Dijkstra，SPFA能处理带负权的边，但如果点进队的次数过多，时间效率就不如前者高
1 #include<cstdio> 2 #include<cstring> 3 #define MAXN 4 #define MAXM 5 #define INF 214748364 6 int n,m,cnt,d[MAXN],heads[MAXN],q[MAXN],pre[MAXN]; 7 int head,tail;//队头、队尾指针 8 bool viss[MAXN];//结点i是否在队列中 9 struct node10 {11 int u,v;12 int next;13 int val;14 }edge[MAXM];15 void add(int x,int y,int z)16 {17 edge[++cnt].u=x;18 edge[cnt].v=y;19 edge[cnt].next=heads[x];20 edge[cnt].val=z;21 heads[x]=cnt;22 }23 void SPFA()24 {25 head=1;tail=2;26 q[1]=1;27 viss[1]=1;//默认1为起点28 while(head<tail)29 {30 for(int i=heads[q[head]];i!=0;i=edge[i].next)31 {32 if(d[q[head]]+edge[i].val<d[edge[i].v])33 {34 d[edge[i].v]=d[q[head]]+edge[i].val;//松弛35 pre[edge[i].v]=i;//记录最短路径，pre存储边的序号36 if(!viss[edge[i].v])//如果v不在队列中，入队37 {38 q[tail++]=edge[i].v;39 viss[edge[i].v]=true;40 }41 }42 }43 viss[q[head]]=false;44 head++;//队头出队45 }46 }47 void print(int x)48 {49 if(edge[x].u==1)50 {51 printf("%d %d ",1,edge[x].v);52 return ;53 }54 print(pre[edge[x].u]);55 printf("%d ",edge[x].v);56 }57 int main()58 {59 scanf("%d%d",&n,&m);60 memset(heads,0,sizeof(heads));61 for(int i=2;i<=n;i++)d[i]=INF;62 int x,y,z;63 for(int i=1;i<=m;i++)64 {65 scanf("%d%d%d",&x,&y,&z);66 add(x,y,z);67 add(y,x,z);//默认输入双向边，所以存储两条方向相反的边68 }69 SPFA();70 printf("%d\n",d[n]);71 x=pre[n];72 print(x);//输出路径73 return 0;74 }
*参考：
http://baike.baidu.com/link?url=FxZ5Ces0YdAHMPmVyJG7f_wJ9-8c6EHreyuDEfHpXsldfk-rfj7ZjtSETKX5Jp14WW28sutbf5zcnLSBcmKzM9zaUVD1Sn9WCwsidDVUhPnSX__1ukG38VjR5g5-5NvK_fjovt-kZIJ1bC4HK1MaBa
图论-单源最短路-SPFA算法
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。