【算法】最短路 - SPFA

2021-01-16 01:13

阅读：788

标签：sizeof 说明 front push class 遍历无限 bellman false

SPFA

即队列优化过的Bellman-Ford算法，可以处理带负权图。

应用于单源最短路。

此外还可以进行负权环的判定，即若第n次操作仍可降低花费，则一定存在负权环。

//Bellman-Ford算法
for (int i = 0; i

//队列优化的Bellman-Ford算法（SPFA）
bool spfa(int s) {
	queueQ;
	memset(inq, 0, sizeof(inq));//标记结点是否在队列中
	memset(cnt, 0, sizeof(cnt));
	for (int i = 0; i  n) return false;
					//如果某个点迭代了超过n次，说明存在可以无限缩短的最短路，即负环
				}
			}
		}
	}
	return true;
}

【算法】最短路 - SPFA

标签：sizeof 说明 front push class 遍历无限 bellman false

原文地址：https://www.cnblogs.com/streamazure/p/12933554.html

上一篇：js将数组对象中某个值相同的对象合并成一个新对象并把这个对象插入到数组当中，增加相同对象的个数

下一篇：Python学习补充 iter partial

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：【算法】最短路 - SPFA
文章链接：http://soscw.com/index.php/essay/42488.html

亲，登录后才可以留言！

【算法】最短路 - SPFA

SPFA

评论

热门文章

推荐文章

最新文章

置顶文章