最短路计数（SPFA）

48 阅读 0 评论 32 点赞

我是靠谱客的博主深情彩虹，最近开发中收集的这篇文章主要介绍最短路计数（SPFA），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Description
给出一个N个顶点M条边的无向无权图，顶点编号为1−N。问从顶点1开始，到其他每个点的最短路有几条。
Input
第一行包含2个正整数N,M，为图的顶点数与边数。
接下来M行，每行2个正整数x,y，表示有一条顶点x连向顶点y的边，请注意可能有自环与重边。
Output
共N行，每行一个非负整数，第i行输出从顶点1到顶点i有多少条不同的最短路，由于答案有可能会很大，你只需要输出ans mod 100003后的结果即可。如果无法到达顶点i则输出0。
**Sample Input 1 **
5 7
1 2
1 3
2 4
3 4
2 3
4 5
4 5
Sample Output 1
1
1
1
2
4
Hint
1到5的最短路有4条，分别为2条1−2−4−5和2条1−3−4−5（由于4−5的边有2条）。
对于20%的数据，N≤100；
对于60%的数据，N≤1000；
对于100%的数据，N<=1000000,M<=2000000
友情提示：即便时限是2s，输入可能依旧会很大，建议使用快读。

本题求单源最短路，并且要计数，可使用SPFA算法。为了节省内存，使用链式前向星存储图。由于是无向无权图，存储一条边的同时要存储一条反向边，故边的最大数目应为2*2000000，这是个坑，如果没注意到，只开了2000000的数组，会导致数组越界，获得Runtime Error。本题要求如果到不了某个点，则输出0，只要把对最短路计数的数组所有元素初值赋为0即可。

接下来对已AC代码进行解读：

#include <stdio.h>
#include <queue>
#include <memory.h>//memset所在头文件
using namespace std;
struct EDGE
{
int v;//到达结点
int val;//边权
int next;//下一条边，为-1时表示边表结束
}edge[4000010];//存储边的数组
int n,m,x,y;//用于接收图的数据
int mod=100003;//答案要模的数
//head[i]表示以i结点为起点的边表的表头
//head[i]=-1时表示结点i没有邻接结点
int head[1000010],cnt=0;
int count[1000010]={0};//最短路计数
int d[1000010];//记录最短路长度
bool visit[1000010]={0};//标记已入队的结点
queue<int> que;
//加一条x->y的边
inline void add_edge(int x,int y)
{
edge[++cnt].v=y;//到达y结点
edge[cnt].val=1;//无权图，边权不妨赋为1
edge[cnt].next=head[x];//插入队头
head[x]=cnt;//更新表头
}
void spfa()
{
//将源点入队
que.push(1);
count[1]=1;
d[1]=0;
visit[1]=true;
int now;//存储出队结点
while(!que.empty())
{
now=que.front();
que.pop();
visit[now]=false;
//根据图的遍历方式，如果一个结点没有邻接结点，没有机会入队
//故不用判断now没有邻接结点
//i等于-1时表示边表到头，-1的补码全是1，取反后变为0
for(int i=head[now];~i;i=edge[i].next)
{
//发现其他最短路，计数
//此时最优解没变，不会影响其他节点的最优解，故不需入队
if(d[now]+edge[i].val==d[edge[i].v])
{
count[edge[i].v]+=count[now];
count[edge[i].v]%=mod;
}
//发现更优最短路，更新d和count
if(d[now]+edge[i].val<d[edge[i].v])
{
count[edge[i].v]=count[now];
count[edge[i].v]%=mod;
d[edge[i].v]=d[now]+edge[i].val;
//如果v不在队列要入队
if(!visit[edge[i].v])
{
que.push(edge[i].v);
visit[edge[i].v]=true;
}
}
}
}
}
int main() {
memset(head,-1,sizeof(head));
scanf("%d %d",&n,&m);
for(int i=0;i<m;++i)
{
scanf("%d %d",&x,&y);
//无向图，加双向边
add_edge(x,y);
add_edge(y,x);
}
//求最短路，故赋初值为最大值
for(int i=0;i<n;++i)
{
d[i+1]=0x7FFFFFFF;
}
spfa();
for(int i=0;i<n;++i)
{
printf("%dn",count[i+1]);
}
return 0;
}