算法札记：SPFA判负环算法的证明

SPFA判负环算法有两种主流判定方式核心都基于图论的抽屉原理完成严谨证明前言SPFA基于bellman-foyd想不通就用bellman-foyd来想想一、基于点入队次数的判定证明‌判定规则‌若图中某节点的入队次数≥总节点数n则图中存在负环。‌证明逻辑‌每次节点入队都对应一次最短路径的松弛更新且更新后该点对应的最短路边数严格递增。当某点入队n次时说明它对应的最短路径边数≥n路径上的节点总数至少为n1。根据抽屉原理n个节点的图中路径必然存在重复出现的顶点也就是形成了环路。而SPFA仅在路径总权值变小时才会触发松弛更新因此这个环路的总边权之和必然为负数即存在负环。二、基于最短路边数的判定证明‌判定规则‌维护cnt数组记录从起点到当前节点的最短路径经过的边数若某点的cnt值≥n则图中存在负环。‌证明逻辑‌若某点的最短路径包含≥n条边路径上的节点数至少为n1再次通过抽屉原理可推导出路径中必然存在重复顶点也就是形成了环路。结合SPFA的松弛更新规则只有路径总权值减小才会更新距离因此该环路的边权和为负直接判定存在负环。这种方式比统计入队次数效率更高是工程中更常用的实现方案。补充说明为了能检测到图中任意位置的负环算法初始化时会将所有节点直接加入队列等价于在原图中新增一个虚拟源点向所有节点连一条权值为0的边保证原图中所有负环都能被虚拟源点可达不会出现漏判的情况。