void SPFA(int src)
{
queue<int> myqueue;
int i,j;
memset(final,0,sizeof(final));
memset(pre,-1,sizeof(pre));
myqueue.push(src);
for(i=0;i<=ncount;++i) //SPFA算法与Dij不同，SPFA初始化时将除源点以外所有点的最短距离初始化无穷大
{
d[i] = maxData;
}
d[src] = 0; //源点最短距离设置成0
final[src] = true;
while(!myqueue.empty()) //SPFA算法可入队列多次
{
int frontint = myqueue.front();myqueue.pop();
final[frontint] = false;
for(i=0;i<=ncount;++i) //遍历所有结点
{
if(dis[frontint][i]<maxData && d[i]>d[frontint]+dis[frontint][i])
{
d[i] = d[frontint]+dis[frontint][i];
pre[i] = frontint; //修改前驱
if(!final[i])
{
final[i] = true;
myqueue.push(i);
}
}
}
}
}
转载于:https://www.cnblogs.com/north_dragon/archive/2010/05/30/1747697.html
相关资源：数据结构—成绩单生成器
