bool spfa()
{
初始化dis[]数组为最大值
初始化dis[源点]=0;
将源点直连的边入队,标记这些边入队次数为1
while (队列不空)
{
出队一条边(u,v)
if (dis[u]+边权(u,v)<dis[v])
{
dis[v]=dis[u]+边权[u][v];
将点v直连的所有边入队,并且这些边的入队次数加一
如果某条边的入队次数等于n说明存在负权回路,返回false,说明没有最短距离
}
}
返回true表示正确计算源点到所有点的最短距离
}
/*
与优化版Dijkstra算法区别:
1、优化版的Dijkstra算法用优先队列选取具有最小值dis[v]的未标记点v,而spfa使用普通队列
2、spfa入队的是边,Dijkstra算法入队的是点v和dis[v]
3、Dijkstra算法要用vis[]数组标记点是否已访问(即已计算出最短距离),spfa不需要标记点
4、spfa算法可以处理负权回路,Dijkstra算法无法处理负权回路。
*/