spfa算法伪代码
  • 板块学术版
  • 楼主NAREKIB
  • 当前回复3
  • 已保存回复3
  • 发布时间2024/8/19 11:45
  • 上次更新2024/8/19 14:36:06
查看原帖
spfa算法伪代码
1415482
NAREKIB楼主2024/8/19 11:45
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算法无法处理负权回路。 
*/ 
2024/8/19 11:45
加载中...