Bellman-Ford 用于求带权有向图中，从一个源点出发到其他顶点的最短距离。它可以处理负权边，这是 Dijkstra 算法无法直接处理的情况。

本文默认顶点编号为 [0, n)，边表示为 from -> to，边权为 weight。

一、Bellman-Ford 算法

1.1 松弛操作

设 dist[v] 表示当前已知的从源点到顶点 v 的最短距离。对于一条边 u -> v，权重为 w，如果：

dist[u] + w < dist[v]

就可以通过 u 更新 v：

dist[v] = dist[u] + w

这一步称为松弛。

1.2 为什么最多遍历 n - 1 次

如果不存在从源点可达的负权环，任意一条简单路径最多包含 n - 1 条边。第 i 轮松弛后，可以保证已经考虑了最多 i 条边组成的路径。

因此，最多进行 n - 1 轮即可得到结果。如果某一轮没有任何距离更新，可以提前结束。

1.3 求最短距离

#include <limits>
#include <vector>

struct Edge {
  int from;
  int to;
  long long weight;
};

struct BellmanFordResult {
  std::vector<long long> distance;
  std::vector<int> previous;
  bool has_negative_cycle = false;
};

BellmanFordResult BellmanFord(
    int vertex_count, int source, const std::vector<Edge>& edges) {
  constexpr long long inf = std::numeric_limits<long long>::max() / 4;

  BellmanFordResult result;
  result.distance.assign(vertex_count, inf);
  result.previous.assign(vertex_count, -1);
  result.distance[source] = 0;

  for (int round = 0; round < vertex_count - 1; ++round) {
    bool changed = false;

    for (const Edge& edge : edges) {
      if (result.distance[edge.from] == inf) {
        continue;
      }

      const long long candidate = result.distance[edge.from] + edge.weight;
      if (candidate < result.distance[edge.to]) {
        result.distance[edge.to] = candidate;
        result.previous[edge.to] = edge.from;
        changed = true;
      }
    }

    if (!changed) {
      break;
    }
  }

  // 第 n 轮仍能松弛，说明存在从 source 可达的负权环。
  for (const Edge& edge : edges) {
    if (result.distance[edge.from] == inf) {
      continue;
    }

    if (result.distance[edge.from] + edge.weight < result.distance[edge.to]) {
      result.has_negative_cycle = true;
      break;
    }
  }

  return result;
}

distance[v] 为 inf 时，表示源点无法到达 v。使用一个足够小的有限值而不是直接使用 LLONG_MAX，是为了避免执行 LLONG_MAX + weight 时发生溢出。

时间复杂度为 O(VE)，空间复杂度为 O(V)，其中 V 是顶点数，E 是边数。

二、恢复最短路径

每次更新 dist[to] 时记录前驱顶点，就可以从终点反向恢复路径：

#include <algorithm>
#include <vector>

std::vector<int> RestorePath(
    int source, int target, const std::vector<int>& previous) {
  std::vector<int> path;

  for (int current = target; current != -1;
       current = previous[current]) {
    path.push_back(current);
    if (current == source) {
      break;
    }
  }

  if (path.empty() || path.back() != source) {
    return {}; // target 不可达
  }

  std::reverse(path.begin(), path.end());
  return path;
}

如果图中存在源点可达的负权环，最短距离没有有限值，此时不应使用 previous 恢复所谓的最短路径。

三、限制路径的边数

有些问题要求路径最多经过 k 条边。不能在同一轮中直接使用本轮刚更新的 dist，否则一轮可能沿着多条边连续传播，实际使用的边数会超过限制。

正确做法是使用两个数组：

  • previous：上一轮最多使用 step - 1 条边的结果。
  • current：这一轮最多使用 step 条边的结果。
#include <limits>
#include <vector>

std::vector<long long> ShortestWithAtMostKEdges(
    int vertex_count, int source, int k, const std::vector<Edge>& edges) {
  constexpr long long inf = std::numeric_limits<long long>::max() / 4;
  std::vector<long long> previous(vertex_count, inf);
  previous[source] = 0;

  for (int step = 1; step <= k; ++step) {
    std::vector<long long> current = previous;

    for (const Edge& edge : edges) {
      if (previous[edge.from] == inf) {
        continue;
      }

      current[edge.to] = std::min(
          current[edge.to], previous[edge.from] + edge.weight);
    }

    previous.swap(current);
  }

  return previous;
}

如果题目限制的是最多 k 个顶点，通常需要转换为最多 k - 1 条边，具体要以题目对起点是否计数的定义为准。

四、SPFA

SPFA 可以看作 Bellman-Ford 的队列实现。它不再每轮遍历所有边，而是只把距离发生变化的顶点加入队列，并从这些顶点继续尝试松弛邻接边。

4.1 算法流程

  1. 将源点加入队列。
  2. 取出一个顶点，尝试松弛它的所有出边。
  3. 如果某个顶点的距离被更新，且它当前不在队列中，则将它加入队列。
  4. 如果某个顶点被成功松弛至少 n 次，说明存在从源点可达的负权环。
#include <limits>
#include <queue>
#include <utility>
#include <vector>

using WeightedGraph = std::vector<std::vector<std::pair<int, long long>>>;

bool SPFA(int source, const WeightedGraph& graph,
          std::vector<long long>& distance) {
  constexpr long long inf = std::numeric_limits<long long>::max() / 4;
  const int vertex_count = static_cast<int>(graph.size());

  distance.assign(vertex_count, inf);
  std::vector<bool> in_queue(vertex_count, false);
  std::vector<int> relax_count(vertex_count, 0);
  std::queue<int> pending;

  distance[source] = 0;
  pending.push(source);
  in_queue[source] = true;

  while (!pending.empty()) {
    const int from = pending.front();
    pending.pop();
    in_queue[from] = false;

    for (const auto& [to, weight] : graph[from]) {
      if (distance[from] + weight >= distance[to]) {
        continue;
      }

      distance[to] = distance[from] + weight;
      if (++relax_count[to] >= vertex_count) {
        return false; // 存在从 source 可达的负权环
      }

      if (!in_queue[to]) {
        pending.push(to);
        in_queue[to] = true;
      }
    }
  }

  return true;
}

SPFA 在很多普通数据上速度较快，但它没有优于 Bellman-Ford 的稳定最坏复杂度，最坏情况下仍可能达到 O(VE)。对于没有负权边的图，通常优先考虑 Dijkstra；对于边数较少或需要检测负权环的场景，可以考虑 Bellman-Ford。

五、总结

  • Bellman-Ford 通过反复松弛所有边求解单源最短路径。
  • 不存在可达负权环时，最多需要 n - 1 轮松弛。
  • 第 n 轮仍然可以松弛，说明存在从源点可达的负权环。
  • 限制边数时必须使用上一轮的距离数组，避免同一轮连续使用多条边。
  • 通过记录前驱顶点可以恢复最短路径。
  • SPFA 使用队列减少无效遍历，但最坏复杂度仍可能达到 O(VE)。

参考资料