实现带邻接表的Bellman-Ford算法：时间复杂度存疑求助

你的Bellman-Ford实现逻辑是正确的，但时间复杂度分析存在偏差，具体纠正如下：

• 第一组嵌套循环的实际复杂度是O(|V||E|)，而非你认为的O(|V|² + |V||E|)。
  外层循环执行|V|-1次，内层的两层循环（遍历所有顶点k，再遍历k的邻接表），总操作数由图中所有边的数量主导：所有顶点的邻接表加起来正好包含全部|E|条边，遍历顶点的O(|V|)开销和O(|E|)相比可以忽略（连通图中|E|≥|V|-1，非连通图中孤立顶点的邻接表为空，遍历无额外开销），因此每次外层循环的复杂度为O(|E|)，整体第一组循环复杂度为O(|V||E|)。
• 负环检测的循环复杂度确实是O(|E|)，因为仅需遍历所有边一次。
• 综上，整个算法的总时间复杂度为O(|V||E|)，与Bellman-Ford算法的公认复杂度一致。

补充说明：你的实现是标准Bellman-Ford算法的简化版本，仅返回起点到目标节点的最短距离，逻辑无问题。如果想优化，可以在每轮松弛后检查目标节点的距离是否不再变化，提前终止外层循环，但这不会改变最坏情况下的时间复杂度。

内容的提问来源于stack exchange，提问作者Michel H