xxx Bellman-Ford算法检测负权环 题目描述 给定一个带权有向图，其中边权可以是正数、负数或零。要求检测图中是否存在从源点出发可达的负权环（即环上各边权重之和为负数的环路）。如果存在这样的环，算法应正确报告；否则给出从源点到各顶点的最短路径。 解题过程 Bellman-Ford算法通过动态规划逐步松弛所有边，最终检测是否存在负权环。以下是详细步骤： 初始化距离数组 创建数组 dist[] ，其中 dist[s] = 0 （源点距离设为0），其余顶点距离初始化为无穷大（如 ∞ ）。 记录前驱节点的数组 pred[] （可选，用于重构路径）。 松弛所有边 对图中的每条边执行以下操作： 对于边 (u, v) ，权重为 w ，若 dist[u] + w < dist[v] ，则更新 dist[v] = dist[u] + w ，并记录 pred[v] = u 。 重复此过程|V| - 1次 （|V|为顶点数），确保最短路径最多经过|V| - 1条边的性质被满足。 检测负权环 额外执行 第|V|次松弛操作 ： 若任意边 (u, v) 满足 dist[u] + w < dist[v] ，则说明存在从源点可达的负权环。 原理：若无负权环，|V| - 1次松弛后应已收敛；若仍可松弛，表明路径可通过负权环无限缩短。 定位负权环（可选） 通过前驱数组 pred[] 回溯：从被松弛的顶点出发，沿前驱节点遍历，直到遇到重复顶点，即可提取环路径。 示例说明 假设图有顶点{A, B, C, D}，边如下： A→B (权重2) B→C (权重-3) C→D (权重1) D→B (权重-1) 源点为A。 初始化：dist[ A ]=0, 其他为∞。 第1轮松弛：更新B=2, C=-1, D=0。 第2轮松弛：更新B=-1（通过D→B），C=-4, D=-3。 第3轮松弛：更新B=-4, C=-7, D=-6。 第4轮（检测）：边D→B满足-6 + (-1) < -4 → 存在负权环{B, C, D}。 关键点 时间复杂度：O(|V|·|E|)，适用于稀疏图。 负权环必须从源点可达才会被检测到。若图包含多个连通分量，需以每个顶点为源点执行算法（或添加虚拟源点）。 与Dijkstra算法不同，Bellman-Ford能处理负权边，但效率较低。