spfa算法的实现过程
什么是spfa算法呢?
弱的摘抄笔记~~
void spfa()
{
queue<int>Q;//队列Q
for(int i=0;i<n;i++)
{
vis[i]=0;
dis[i]=INF;
}
dis[0]=0;//距离
Q.push(0);
vis[0]=1;//访问
while(!Q.empty())//直到队列为0
{
int h=Q.front();
Q.pop();
vis[h]=0;//不在队列里
for(int i=0;i<n;i++)//寻找后续点
{
int val=s[h][i]-'0';
int to=i;
if(val==0)
continue;
if(dis[h]+val<dis[to])//值变小了,需要入队
{
dis[to]=dis[h]+val;
if(!vis[to])
{
vis[to]=1;
Q.push(to);
}
}
}
}
}