如何在Floyd-Warshall算法中添加负权环检测逻辑

以下是用于最短路径检测的Floyd-Warshall算法伪代码：

你的判断是对的，该功能扩展完全可行，且不需要改动原有算法的核心流程，仅需在原有逻辑执行完成后增加一步校验即可，核心逻辑和实现步骤如下：

检测原理 #

Floyd-Warshall通过逐轮引入中间节点的方式，动态更新任意两点间的最短路径长度。如果图中存在负权环，那么环上的节点可以通过绕环行走无限次压缩路径长度，最终会出现节点到自身的最短路径长度小于0的情况——正常无负权环的图里，节点到自身的最短路径就是原地不动，长度为0。

具体实现步骤 #

• 初始化阶段：沿用原有算法的初始化逻辑，将距离矩阵dist的对角线元素（即节点到自身的距离）dist[i][i]全部设为0，存在直接边的节点对赋值为对应边权，无直接连边的节点对赋值为无穷大。
• 核心更新阶段：完全保留原有三重循环的更新逻辑，逐次以每个节点为中间点k，遍历所有节点对(i,j)，如果dist[i][j] > dist[i][k] + dist[k][j]就更新dist[i][j]为更小值。
• 校验判断阶段：三重循环执行完毕后，遍历距离矩阵的所有对角线元素：
  • 只要存在任意一个节点i满足dist[i][i] < 0，即可判定图中存在负权环
  • 如果所有节点的dist[i][i]都等于0，即可判定图中不存在负权环

补充说明：如果需要进一步定位负权环的具体组成，只需要在算法更新过程中同步维护路径前驱矩阵，找到dist[i][i]<0的节点后沿前驱指针回溯即可还原环路径，仅做存在性判断不需要额外存储前驱信息。

内容的提问来源于stack exchange，提问作者Tryer outer