最短路径⚓︎

最短路径问题指找到图中两个节点之间的最短路径。根据图的性质（有向图或无向图，带权重或不带权重，是否存在负权边等），可以使用不同的算法来解决最短路径问题。

Dijkstra 算法⚓︎

$\text{Dijkstra}$ 算法是一种用于计算单源最短路径的贪心算法，适用于边权重非负的图。它通过逐步扩展已知最短路径的节点集合，最终找到从起始节点到所有其他节点的最短路径。

使用优先队列（通常是最小堆）来高效地选择当前距离最短的节点的方法，算法的时间复杂度为 $O((V + E) \log V)$ ，其中 $V$ 是节点数， $E$ 是边数。

Tip

如果图中存在负权边， $\text{Dijkstra}$ 算法可能无法正确计算最短路径。此时可以考虑使用 $\text{Bellman-Ford}$ 或 $\text{SPFA}$ 算法。

C++

#include <cstdint>
#include <functional>
#include <iostream>
#include <queue>
#include <utility>
#include <vector>
using namespace std;

using PII = pair<int64_t, int64_t>;

void dijkstra(int n, const vector<vector<PII>> &graph, int64_t source) {
  vector<int64_t> distance(n + 1, INT64_MAX);
  vector<bool> visit(n + 1, false);
  distance[source] = 0;

  priority_queue<PII, vector<PII>, greater<>> pq;  // {distance, node}
  pq.emplace(0, source);

  while (!pq.empty()) {
    auto [d, u] = pq.top();
    pq.pop();
    if (visit[u]) { continue; }
    visit[u] = true;
    for (auto [v, w] : graph[u]) {
      if (distance[u] + w < distance[v]) {  // 发现更短路径
        distance[v] = distance[u] + w;
        pq.emplace(distance[v], v);
      }
    }
  }

  for (int64_t i = 1; i <= n; ++i) { cout << distance[i] << " "; }
}

int main() {
  int n, m, s;
  cin >> n >> m >> s;
  vector<vector<PII>> graph(n + 1);
  for (int i = 0; i < m; ++i) {
    int u, v;
    int64_t w;
    cin >> u >> v >> w;
    graph[u].emplace_back(v, w);
  }
  dijkstra(n, graph, s);
  return 0;
}

分层最短路径⚓︎

分层图是将原图中的每个节点复制多份，形成多个层次的节点，然后在这些层次之间添加边，从而将某些复杂的路径问题转化为简单的最短路径问题。分层图常用于解决带有额外约束条件的最短路径问题，例如限制路径长度、限制经过特定节点等。

使用 $\text{Dijkstra}$ 算法在分层图上计算最短路径时通常需要增加节点的状态信息，例如当前所在的层数或已经经过的特定节点数量。这样可以确保算法在计算最短路径时考虑到这些额外的约束条件。

飞行路线

给定一个有 $n$ 个节点和 $m$ 条边的有向图，每条边有一个权重。找到从节点 $s$ 到节点 $t$ 的最短路径，允许最多将 $k$ 条边的权重视为 $0$ 。

C++

#include <cstdint>
#include <functional>
#include <iostream>
#include <queue>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;

using PII  = pair<int64_t, int64_t>;
using TIII = tuple<int64_t, int64_t, int64_t>;

int64_t dijkstra(vector<vector<PII>> &graph, int64_t source, int64_t end, int64_t k) {
  int64_t n = graph.size();
  vector<vector<int64_t>> distance(n, vector<int64_t>(k + 1, INT32_MAX));
  vector<vector<bool>> visit(n, vector<bool>(k + 1, false));
  distance[source][0] = 0;

  priority_queue<TIII, vector<TIII>, greater<>> pq;  // {distance, node, k_used}
  pq.emplace(0, source, 0);

  while (!pq.empty()) {
    auto [d, u, k_used] = pq.top();
    pq.pop();
    if (u == end) { return d; }
    if (visit[u][k_used]) { continue; }
    visit[u][k_used] = true;
    for (auto [v, w] : graph[u]) {
      if (distance[u][k_used] + w < distance[v][k_used]) {  // 不使用
        distance[v][k_used] = distance[u][k_used] + w;
        pq.emplace(distance[v][k_used], v, k_used);
      }
      if (k_used < k && distance[u][k_used] + 0 < distance[v][k_used + 1]) {  // 使用
        distance[v][k_used + 1] = distance[u][k_used];
        pq.emplace(distance[v][k_used + 1], v, k_used + 1);
      }
    }
  }
  return -1;
}

int main() {
  int64_t n, m, k;
  cin >> n >> m >> k;
  int64_t s, t;
  cin >> s >> t;
  vector<vector<PII>> graph(n);
  for (int64_t i = 0; i < m; ++i) {
    int64_t u, v, w;
    cin >> u >> v >> w;
    graph[u].emplace_back(v, w);
    graph[v].emplace_back(u, w);  // 无向图
  }
  cout << dijkstra(graph, s, t, k) << '\n';
  return 0;
}

小雨坐地铁

每条线路有一个固定的乘车费用，且每条线路上相邻站点之间的距离相同。可以在任意线路的起点站出发，并且每次换乘时都需要支付该线路的乘车费用。请你计算从起点站 $s$ 到终点站 $t$ 的最少花费。

C++

#include <cstdint>
#include <functional>
#include <iostream>
#include <queue>
#include <tuple>
#include <vector>
using namespace std;

using TIII = tuple<int64_t, int64_t, int64_t>;

int64_t dijkstra(const vector<vector<TIII>> &graph, const vector<int64_t> &cost,
                 const vector<int64_t> &start_lines, int64_t source, int64_t target) {
  if (source == target) { return 0; }
  int64_t n = graph.size();
  int64_t m = cost.size();
  vector<vector<int64_t>> distance(n, vector<int64_t>(m, INT64_MAX));
  vector<vector<bool>> visit(n, vector<bool>(m, false));

  priority_queue<TIII, vector<TIII>, greater<>> pq;  // {distance, node, line_id}
  // 起点可以在不同线路的站点出发, 初始距离为该线路的花费
  for (int64_t line_id : start_lines) {
    distance[source][line_id] = cost[line_id];
    pq.emplace(distance[source][line_id], source, line_id);
  }
  while (!pq.empty()) {
    auto [d, u, u_line] = pq.top();
    pq.pop();
    if (u == target) { return d; }
    if (visit[u][u_line]) { continue; }  // 已经处理过
    visit[u][u_line] = true;

    for (auto [v, w, v_line] : graph[u]) {
      if (v_line == u_line) {                                 // 在线路内移动
        if (distance[u][u_line] + w < distance[v][v_line]) {  // 发现更短路径
          distance[v][v_line] = distance[u][u_line] + w;
          pq.emplace(distance[v][v_line], v, v_line);
        }
      } else {  // 换乘
        if (distance[u][u_line] + w + cost[v_line] < distance[v][v_line]) {
          distance[v][v_line] = distance[u][u_line] + w + cost[v_line];
          pq.emplace(distance[v][v_line], v, v_line);
        }
      }
    }
  }
  return -1;
}

int main() {
  int64_t n, m, s, t;
  cin >> n >> m >> s >> t;
  vector<vector<TIII>> graph(n + 1);  // <to, weight, line_id>
  vector<int64_t> cost(m + 1);        // 每条线的花费, 从1开始编号
  vector<int64_t> start_lines;        // 起点所在的线路
  for (int64_t i = 1; i <= m; ++i) {
    int64_t a, b, c;
    cin >> a >> b >> c;
    cost[i] = a;
    // 记录每个站点对应的线路
    for (int64_t j = 0, from; j < c; ++j) {
      int64_t to;
      cin >> to;
      if (j > 0) {  // 连接相邻站点
        graph[from].emplace_back(to, b, i);
        graph[to].emplace_back(from, b, i);
      }
      // 起点可以在不同线路的站点出发
      if (to == s) { start_lines.emplace_back(i); }
      from = to;
    }
  }

  cout << dijkstra(graph, cost, start_lines, s, t) << "\n";
  return 0;
}

米小游的异或最短路

给定一个带权有向图，在路径上可以选择连续的一段边（只能使用一次）将它们的权值都异或上整数 $x$ ，然后计算该路径的边权和。

求对每个节点，从 $1$ 出发的最小可能代价（可以不使用异或操作）。

需要网站会员提交

C++

#include <algorithm>
#include <cstdint>
#include <functional>
#include <iostream>
#include <queue>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;

using PII  = pair<int64_t, int64_t>;
using TIII = tuple<int64_t, int64_t, int64_t>;

int main() {
  int64_t n, m, x;
  cin >> n >> m >> x;
  vector<vector<PII>> graph(n + 1);
  for (int64_t i = 0; i < m; ++i) {
    int64_t u, v, w;
    cin >> u >> v >> w;
    graph[u].emplace_back(v, w);
  }

  // 每个节点三种状态: 未开始异或, 已开始未结束异或, 已结束异或
  vector<vector<int64_t>> distance(n + 1, vector<int64_t>(3, INT64_MAX));
  vector<vector<bool>> visit(n + 1, vector<bool>(3, false));
  // 第一项为距离, 第二项为节点,
  // 第三项为状态(0:未开始异或,1:已开始未结束异或,2:已结束异或)
  priority_queue<TIII, vector<TIII>, greater<>> pq;
  pq.emplace(0, 1, 0);
  distance[1] = {0, 0, 0};

  while (!pq.empty()) {
    auto [dis, u, state] = pq.top();
    pq.pop();
    // 如果只需找到某一个点的最短路径, 可以在这里加一个判断相等就直接break
    if (visit[u][state]) { continue; }  // 已经处理过
    visit[u][state] = true;
    for (auto [v, w] : graph[u]) {
      if (state == 0) {                             // 未开始异或, 可以选择开始异或或者不开始异或
        if (distance[u][0] + w < distance[v][0]) {  // 不开始异或
          distance[v][0] = distance[u][0] + w;
          pq.emplace(distance[v][0], v, 0);
        }
        if (distance[u][0] + (w ^ x) < distance[v][1]) {  // 开始异或
          distance[v][1] = distance[u][0] + (w ^ x);
          pq.emplace(distance[v][1], v, 1);
        }
      } else if (state == 1) {  // 已开始未结束异或, 可以选择继续异或或者结束异或
        if (distance[u][1] + (w ^ x) < distance[v][1]) {  // 继续异或
          distance[v][1] = distance[u][1] + (w ^ x);
          pq.emplace(distance[v][1], v, 1);
        }
        if (distance[u][1] + w < distance[v][2]) {  // 结束异或
          distance[v][2] = distance[u][1] + w;
          pq.emplace(distance[v][2], v, 2);
        }
      } else if (state == 2) {  // 结束异或之后只能保持结束异或状态
        if (distance[u][2] + w < distance[v][2]) {
          distance[v][2] = distance[u][2] + w;
          pq.emplace(distance[v][2], v, 2);
        }
      }
    }
  }
  for (int64_t i = 1; i <= n; ++i) {
    int64_t ans = min({distance[i][0], distance[i][1], distance[i][2]});
    if (ans == INT64_MAX) {
      cout << -1 << " ";
    } else {
      cout << ans << " ";
    }
  }
}

Floyd-Warshall 算法⚓︎

$\text{Floyd-Warshall}$ 算法是一种用于计算所有节点对之间最短路径的动态规划算法，适用于边权重可以为负但不含负环的图。它通过逐步考虑每个节点作为中间节点，更新所有节点对之间的最短路径。

时间复杂度为 $O(V^3)$ ，其中 $V$ 是节点数。

$\text{Floyd-Warshall}$ 算法的转移方程为：

$distance[i][j] = \min(distance[i][j], distance[i][k] + distance[k][j])$

其中 $k$ 是当前考虑的中间节点。

$\text{Floyd-Warshall}$ 算法不仅可以计算最短路径，还可以用于检测图中是否存在负环。如果在算法执行完毕后，发现 $distance[i][i] < 0$ ，则说明图中存在负环。

Clear And Present Danger S

给定一个有向图，从节点 $1$ 出发，经过一系列节点，最后到达节点 $m$ 。图中每条边有一个权重，表示通过该边的代价。请计算从节点 $1$ 到节点 $m$ 的最小代价。

C++

#include <cstdint>
#include <iostream>
#include <vector>
using namespace std;

void solve() {}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int64_t n, m;
  cin >> n >> m;
  vector<vector<int64_t>> distance(n + 1, vector<int64_t>(n + 1, INT64_MAX));
  vector<int64_t> path(m);
  for (int64_t i = 0; i < m; ++i) { cin >> path[i]; }
  for (int64_t i = 1; i <= n; ++i) {
    for (int64_t j = 1; j <= n; ++j) { cin >> distance[i][j]; }
  }
  // floyd
  for (int k = 1; k <= n; ++k) {  // 枚举中转点
    for (int i = 1; i <= n; ++i) {
      for (int j = 1; j <= n; ++j) {
        // 找到更短路径
        if (distance[i][k] != INT64_MAX && distance[k][j] != INT64_MAX
            && distance[i][k] + distance[k][j] < distance[i][j]) {
          distance[i][j] = distance[i][k] + distance[k][j];
        }
      }
    }
  }
  int64_t ans = 0;
  for (int64_t i = 1; i < m; ++i) { ans += distance[path[i - 1]][path[i]]; }
  cout << ans << "\n";

  return 0;
}

从 $distance$ 数组中可以直接读取任意两点之间的最短路径长度，并且可以通过维护一个 $pass$ 数组来记录路径上的中间节点，从而重构最短路径。

路径重构

C++

void floyd(vector<vector<int64_t>> &distance) {
  int n = distance.size();
  vector<vector<int64_t>> pass(n, vector<int64_t>(n, -1));  // 记录路径中转点
  for (int k = 0; k < n; ++k) {  // 枚举中转点
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < n; ++j) {
        // 找到更短路径
        if (distance[i][k] != INT64_MAX && distance[k][j] != INT64_MAX
            && distance[i][k] + distance[k][j] < distance[i][j]) {
          distance[i][j] = distance[i][k] + distance[k][j];
          pass[i][j]     = k;  // 记录中转点
        }
      }
    }
  }

  // 重构路径
  vector<int64_t> path;
  function<void(int64_t, int64_t)> get_path = [&](int64_t u, int64_t v) {
    if (distance[u][v] == INT64_MAX) { return; }  // 不可达
    if (pass[u][v] == -1) {  // u->v 之间没有中转点
      if (path.empty()) { path.push_back(u); } // 只在第一次调用时添加起点
      path.push_back(v); // 添加终点
      return;
    }
    int64_t k = pass[u][v];
    get_path(u, k);
    get_path(k, v);
  };

Bellman-Ford 算法⚓︎

$\text{Bellman-Ford}$ 算法是一种用于计算单源最短路径的动态规划算法，适用于边权重可以为负但不含负环的图。它通过逐步松弛所有边，最终找到从起始节点到所有其他节点的最短路径。

时间复杂度为 $O(V \cdot E)$ ，其中 $V$ 是节点数， $E$ 是边数。

$\text{Bellman-Ford}$ 算法的核心思想是：对于每一条边 $(u, v)$ ，如果通过 $u$ 到达 $v$ 的路径比当前已知的最短路径更短，则更新最短路径。

具体步骤如下：

初始化：将起始节点 $s$ 的距离设为 $0$ ，其他节点的距离设为无穷大
松弛操作：对每一条边 $(u, v)$ ，如果 $distance[u] + w(u, v) < distance[v]$ ，则更新 $distance[v] = distance[u] + w(u, v)$
重复执行松弛操作 $V-1$ 次
检测负环：如果在第 $V$ 次松弛操作中仍然能够更新某条边，则说明图中存在负环

全局负环检测

如果只需要检测图中是否存在负环，新增一个虚拟源点，连接到所有节点，边权重为0。

【模板】负环

给定一个有向图，判断图中是否存在从节点 $1$ 出发可达的负环。

C++

#include <cstdint>
#include <iostream>
#include <tuple>
#include <vector>
using namespace std;

void solve() {
  const int64_t INF = INT64_MAX;

  int64_t n, m;
  cin >> n >> m;
  using TIII = tuple<int64_t, int64_t, int64_t>;  // (from, to, weight)
  vector<TIII> edges;
  for (int64_t i = 0; i < m; ++i) {
    int64_t u, v, w;
    cin >> u >> v >> w;
    if (w < 0) {
      edges.emplace_back(u, v, w);
    } else {
      edges.emplace_back(u, v, w);
      edges.emplace_back(v, u, w);
    }
  }
  int64_t source = 1;

  vector<int64_t> backup;
  vector<int64_t> distance(n + 1, INF);
  distance[source] = 0;
  // 最多松弛n-1次
  for (int i = 0; i < n - 1; ++i) {
    backup = distance;
    for (const auto &edge : edges) {
      auto [from, to, weight] = edge;
      // 松弛操作
      if (backup[from] != INF && distance[to] > backup[from] + weight) {
        distance[to] = backup[from] + weight;
      }
    }
  }
  // 检测负环
  for (const auto &edge : edges) {
    auto [from, to, weight] = edge;
    if (distance[from] != INF && distance[to] > distance[from] + weight) {  // 有负环
      cout << "YES\n";
      return;
    }
  }
  cout << "NO\n";
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int64_t t;
  cin >> t;
  while ((t--) != 0) { solve(); }
}

SPFA 算法⚓︎

$\text{SPFA}$ （Shortest Path Faster Algorithm）算法是 $\text{Bellman-Ford}$ 算法的一种优化版本，适用于边权重可以为负但不含负环的图。

$\text{SPFA}$ （Shortest Path Faster Algorithm）算法的核心思想是：使用队列来存储需要松弛的节点，只有当一个节点的距离被更新时，才将其加入队列进行松弛操作。

时间复杂度为 $O(kE)$ ，其中 $k$ 是每条边被松弛的平均次数， $E$ 是边数。在最坏情况下， $\text{SPFA}$ 的时间复杂度仍然是 $O(VE)$ （~~xxxx，它死了~~）。

全局负环检测

如果只需要检测图中是否存在负环，新增一个虚拟源点，连接到所有节点，边权重为0。

【模板】负环

给定一个有向图，判断图中是否存在从节点 $1$ 出发可达的负环。

C++

#include <cstdint>
#include <iostream>
#include <queue>
#include <utility>
#include <vector>
using namespace std;

void solve() {
  int64_t n, m;
  cin >> n >> m;
  using PII = pair<int, int>;
  vector<vector<PII>> graph(n + 1);
  for (int64_t i = 0; i < m; ++i) {
    int64_t u, v, w;
    cin >> u >> v >> w;
    if (w < 0) {
      graph[u].emplace_back(v, w);
    } else {
      graph[u].emplace_back(v, w);
      graph[v].emplace_back(u, w);
    }
  }
  int64_t source = 1;

  vector<int64_t> distance(n + 1, INT64_MAX);
  vector<bool> in_queue(n + 1, false);  // 标志是否在队列中
  vector<int64_t> counter(n + 1, 0);    // 记录松弛次数，用于检测负环

  distance[source] = 0;
  queue<int64_t> q;
  q.emplace(source);
  in_queue[source] = true;  // 标记已入队
  counter[source]  = 1;     // 松弛次数加1

  while (!q.empty()) {
    int64_t u = q.front();
    q.pop();
    in_queue[u] = false;
    // 尝试使用该点，更新其他点的最短距离
    for (auto [v, w] : graph[u]) {
      if (distance[u] + w < distance[v]) {
        distance[v] = distance[u] + w;
        if (in_queue[v]) { continue; }  // 已入队
        counter[v]++;                   // 松弛次数加1
        if (counter[v] > n - 1) {       // 松弛次数超过n-1次，有负环
          cout << "YES\n";
          return;
        }
        q.emplace(v);        // 入队
        in_queue[v] = true;  // 标记已入队
      }
    }
  }
  cout << "NO\n";
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int64_t t;
  cin >> t;
  while ((t--) != 0) { solve(); }
}

Johnson 算法⚓︎

如果要求全源最短路径：

没有负边：对每个节点调用 $\text{Dijkstra}$ 算法，时间复杂度 $O(V (V + E) \log V)$
有负边：
- 使用 $n$ 次 $\text{Bellman-Ford}$ 算法，时间复杂度 $O(V^2 E)$
- 使用 $\text{Floyd}$ 算法，时间复杂度 $O(V^3)$

$\text{Johnson}$ 算法是一种用于计算所有节点对之间最短路径的算法，适用于边权重可以为负但不含负环的图。它结合了 $\text{Bellman-Ford}$ 和 $\text{Dijkstra}$ 算法的优点，能够高效地处理稀疏图。

$\text{Johnson}$ 算法的主要步骤如下：

新增一个虚拟节点 $q$ ，连接到图中的所有节点，边权重为 $0$ 。
使用 $\text{Bellman-Ford}$ 算法从虚拟节点 $q$ 出发，计算从 $q$ 到所有其他节点的最短路径距离 $h(v)$ 。
对图中的每条边 $(u, v)$ ，重新计算边权重为 $w'(u, v) = w(u, v) + h(u) - h(v)$ ，这样所有边的权重都变为非负。
对每个节点 $u$ ，使用 $\text{Dijkstra}$ 算法计算从 $u$ 出发到所有其他节点的最短路径距离 $d'(u, v)$ 。
最终的最短路径距离为 $d(u, v) = d'(u, v) - h(u) + h(v)$ 。

若第 4 步使用堆优化 $\text{Dijkstra}$ ，则时间复杂度可写为：

$O\big(VE + V(E+V)\log V\big)$

其中第一项来自一次 $\text{Bellman-Ford}$ ，第二项来自对每个点执行一次堆优化 $\text{Dijkstra}$ 。在稀疏图中，通常可进一步记作 $O(VE \log V)$ 量级。

全局负环检测

$\text{Johnson}$ 算法不能处理含有负环的图。如果在第 2 步中 $\text{Bellman-Ford}$ 算法检测到负环，则说明图中存在负环，算法终止。

【模板】全源最短路（Johnson）

C++

#include <cstdint>
#include <functional>
#include <iostream>
#include <queue>
#include <utility>
#include <vector>
using namespace std;

using PII         = pair<int64_t, int64_t>;

const int64_t INF = 1e9;

vector<int64_t> dijkstra(vector<vector<PII>> &graph, int64_t source, vector<int64_t> &distance) {
  int64_t n = graph.size();
  distance  = vector<int64_t>(n, INF);
  vector<bool> visit(n);

  priority_queue<PII, vector<PII>, greater<>> pq;
  pq.emplace(0, source);
  distance[source] = 0;

  while (!pq.empty()) {
    auto [dis, u] = pq.top();
    pq.pop();
    if (visit[u]) { continue; }
    visit[u] = true;
    for (auto [v, w] : graph[u]) {
      if (distance[u] + w < distance[v]) {
        distance[v] = distance[u] + w;
        pq.emplace(distance[v], v);
      }
    }
  }
  return distance;
}

vector<int64_t> SPFA(const vector<vector<PII>> &graph, int64_t source) {
  int64_t n = graph.size();
  vector<int64_t> distance(n, INF);
  vector<bool> in_queue(n);    // 标志是否在队列中
  vector<int64_t> counter(n);  // 记录松弛次数，用于检测负环

  distance[source] = 0;
  queue<int64_t> q;
  q.emplace(source);
  in_queue[source] = true;
  counter[source]  = 1;

  while (!q.empty()) {
    int64_t u = q.front();
    q.pop();
    in_queue[u] = false;
    for (auto [v, w] : graph[u]) {
      if (distance[u] + w < distance[v]) {
        distance[v] = distance[u] + w;
        if (in_queue[v]) { continue; }  // 已入队
        counter[v]++;
        if (counter[v] > n - 1) {  // 有负环
          return {};
        }
        q.emplace(v);
        in_queue[v] = true;
      }
    }
  }
  return distance;
}

void johnson(int n, vector<vector<PII>> &graph) {
  // 2. 使用SPFA从s出发计算每个节点的最短距离h(v)
  vector<int64_t> h = SPFA(graph, 0);
  // 有负环, 无法使用Johnson算法
  if (h.empty()) {
    cout << -1 << "\n";
    return;
  }
  // 3. 对每条边(u, v)重新标注边权 w'(u, v) = w(u, v) + h(u) - h(v)
  for (int64_t u = 1; u <= n; ++u) {
    for (auto &[v, w] : graph[u]) { w = w + h[u] - h[v]; }
  }

  // 4. 对每个节点使用Dijkstra计算最短路径
  vector<vector<int64_t>> distances(n + 1);
  for (int64_t u = 1; u <= n; ++u) {
    dijkstra(graph, u, distances[u]);
    // 最终结果 distance(u, v) = distance'(u, v) - h(u) + h(v)
    for (int64_t v = 1; v <= n; ++v) {
      if (distances[u][v] != INF) { distances[u][v] = distances[u][v] - h[u] + h[v]; }
    }
  }

  for (int64_t u = 1; u <= n; ++u) {
    int64_t sum = 0;
    for (int64_t j = 1; j <= n; ++j) { sum += j * distances[u][j]; }
    cout << sum << "\n";
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int64_t n, m;
  cin >> n >> m;
  vector<vector<PII>> graph(n + 1);
  for (int64_t i = 0; i < m; ++i) {
    int64_t u, v, w;
    cin >> u >> v >> w;
    graph[u].emplace_back(v, w);
  }
  // 1. 增加虚拟节点s, 编号为0, 连接图中所有节点, 边权为0
  graph[0].resize(n);
  for (int64_t i = 1; i <= n; ++i) { graph[0][i - 1] = {i, 0}; }
  johnson(n, graph);
  return 0;
}

其他最短路径问题⚓︎

经过恰好 k 条边的路径数量⚓︎

给定一个图，计算从起点 $s$ 到终点 $t$ 的经过恰好 $k$ 条边的路径数量（ $walk$ ，允许重复经过节点或边）。

假设图的邻接矩阵为 $A$ ，其中 $A[i][j]$ 表示从节点 $i$ 到节点 $j$ 是否有边（1 表示有边，0 表示无边）。那么 $A^k$ 的第 $i$ 行第 $j$ 列的值表示从节点 $i$ 到节点 $j$ 经过恰好 $k$ 条边的路径数量。

可以使用矩阵快速幂来解决这个问题。朴素的矩阵乘法时间复杂度为 $O(n^3)$ ，计算 $A^k$ 的时间复杂度为 $O(n^3 \log k)$ 。

证明

$A^{k}[i][j]$ 可以通过以下方式计算：

$A^{k}[i][j] = \sum_{m=1}^{n} A[i][m] \cdot A^{k-1}[m][j]$

其中 $n$ 是图中的节点数。这个公式表示从节点 $i$ 出发，经过一条边到达节点 $m$ ，然后从节点 $m$ 出发经过 $k-1$ 条边到达节点 $j$ 的所有可能路径数量的总和。

通过数学归纳法可以证明这个公式的正确性：

当 $k=1$ 时，有 $A^{1} = A$ ，显然成立。
归纳假设：假设对于某个 $k \geq 1$ ，公式成立，即 $A^{k}[i][j]$ 表示从节点 $i$ 到节点 $j$ 经过恰好 $k$ 条边的路径数量。
归纳步骤：考虑 $k+1$ 的情况。第 $k+1$ 步可以先从节点 $i$ 出发，经过一条边到达节点 $m$ ，然后从节点 $m$ 出发经过 $k$ 条边到达节点 $j$ 。根据归纳假设， $A^{k}[m][j]$ 表示从节点 $m$ 到节点 $j$ 经过恰好 $k$ 条边的路径数量。因此：

$A^{k+1}[i][j] = \sum_{m=1}^{n} A[i][m] \cdot A^{k}[m][j]$

根据矩阵乘法的定义，有：

$A^{k+1} = A \cdot A^{k}$

因此归纳步骤成立。

综上所述，通过矩阵乘法计算邻接矩阵的幂次，可以得到从起点到终点经过恰好 $k$ 条边的路径数量。

变种问题

恰好 $k$ 条边的最短路： $(min，+)$ 代数下求 $A^k$ 。
如果需要计算从起点 $s$ 到终点 $t$ 的经过最多 $k$ 条边的路径数量，可以计算 $A^1 + A^2 + ... + A^k$ ，然后取出结果矩阵中的第 $s$ 行第 $t$ 列的值。
如果需要计算从起点 $s$ 到终点 $t$ 的经过至少 $k$ 条边的路径数量，可以计算总路径数量减去经过少于 $k$ 条边的路径数量。

定长最短路径⚓︎

给定一个带权有向图，计算从任意起点 $s$ 到任意终点 $t$ 的经过恰好 $k$ 条边的最短路径长度。

可以使用类似于 $\text{Floyd-Warshall}$ 算法的动态规划方法来解决这个问题。定义 $dp^{m} [i][j]$ 表示从节点 $i$ 到节点 $j$ 经过恰好 $m$ 条边的最短路径长度。

初始条件为：

当 $m=0$ 时， $dp^{0}[i][i] = 0$ ，表示从节点 $i$ 到节点 $i$ 经过 $0$ 条边的路径长度为 $0$ 。
当 $m=1$ 时，如果存在一条边从节点 $i$ 到节点 $j$ ，则 $dp^{1}[i][j] = w(i, j)$ ，其中 $w(i, j)$ 是边 $(i, j)$ 的权重。

转移方程为：

$dp^{m}[i][j] = \min_{p \in \text{adj}(j)} (dp^{m-1}[i][p] + w(p, j))$

其中 $p$ 是所有与节点 $j$ 相邻的节点。

最终答案为 $dp^{k}[s][t]$ 。

时间复杂度为 $O(V^3 \cdot k)$ ，其中 $V$ 是节点数， $k$ 是路径长度。

利用矩阵快速幂可以将时间复杂度优化到 $O(V^3 \log k)$ 。将图的邻接矩阵表示为一个矩阵 $A$ ，其中 $A[i][j]$ 表示从节点 $i$ 到节点 $j$ 的边权重（如果没有边则为无穷大）。转移方程就表示为：

$dp^{m}[i][j] = \min_{1 \leq p \leq n} (dp^{m-1}[i][p] + A[p][j])$

这可以通过矩阵 $A$ 在 $(\min, +)$ 代数下的 $k$ 次幂 $A^k$ 来计算，于是得到：

$dp^{k} = dp^{k-1} \otimes A = dp^{k-2} \otimes A^{2} = \dots = dp^{0} \otimes A^{k}$

如果固定起点 $s$ ，状态定义可以直接定义为从节点 $s$ 到节点 $j$ 经过恰好 $m$ 条边的最短路径长度，可以省略掉一维。状态转移时也无需枚举起点。

$dp^{m}[j]$ 表示从节点 $s$ 到节点 $j$ 经过恰好 $m$ 条边的最短路径长度。

初始条件为：

$dp^{0}[s] = 0$ ，表示从节点 $s$ 到节点 $s$ 经过 $0$ 条边的路径长度为 $0$ 。
对于节点 $j \neq s$ ， $dp^{0}[j] = \infty$ ，表示无法通过 $0$ 条边到达其他节点。

转移方程为：

$dp^{m}[j] = \min_{p \in \text{adj}(j)} (dp^{m-1}[p] + w(p, j))$

其中 $p$ 是所有与节点 $j$ 相邻的节点。

牛站

给定一个有 $t$ 条边的无向图，每条边有一个长度。计算从节点 $s$ 到节点 $e$ 经过恰好 $n$ 条边的最短路径长度。

重复边

输入数据中可能存在重复边，需要取最短的边权。

动态规划矩阵快速幂优化

TLE

即使使用固定起点减少一维状态，时间复杂度仍然是 $O(n \cdot m^2)$ ，其中 $m$ 是节点数， $n$ 是路径长度，仍然会超时。

MLE

如果使用三维数组存储状态会导致内存超限，因为步数 $n$ 可能非常大（例如 $10^5$ ）。

C++

#include <algorithm>
#include <cstdint>
#include <iostream>
#include <map>
#include <tuple>
#include <vector>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  using TIII = tuple<int, int, int>;

  int n, t, s, e;
  cin >> n >> t >> s >> e;
  vector<TIII> edges(t);
  map<int, int> point_id;
  for (int i = 0; i < t; ++i) {
    int l, x, y;
    cin >> l >> x >> y;
    if (point_id.count(x) == 0) { point_id[x] = point_id.size(); }
    if (point_id.count(y) == 0) { point_id[y] = point_id.size(); }
    edges[i] = {l, point_id[x], point_id[y]};
  }
  s         = point_id[s];
  e         = point_id[e];
  int m     = point_id.size();

  using VI  = vector<int>;
  using VVI = vector<VI>;

  VVI graph(m, VI(m, INT32_MAX / 2));
  for (const auto &[l, x, y] : edges) { graph[x][y] = graph[y][x] = min(graph[x][y], l); }

  VVI dp(m, VI(m, INT32_MAX / 2));
  for (int j = 0; j < m; ++j) { dp[j][j] = 0; }
  VVI dp_next(m, VI(m, INT32_MAX / 2));
  for (int i = 1; i <= n; ++i) {  // 枚举步数
    fill(dp_next.begin(), dp_next.end(), VI(m, INT32_MAX / 2));
    for (int j = 0; j < m; ++j) {      // 枚举起点
      for (int k = 0; k < m; ++k) {    // 枚举终点
        for (int l = 0; l < m; ++l) {  // 枚举中转点
          dp_next[j][k] = min(dp_next[j][k], dp[j][l] + graph[l][k]);
        }
      }
    }
    dp = dp_next;
  }
  cout << dp[s][e] << "\n";
  return 0;
}

C++

#include <algorithm>
#include <cmath>
#include <cstdint>
#include <iostream>
#include <map>
#include <tuple>
#include <vector>
using namespace std;

// 矩阵乘法，定义为 "最小化加法"（最短路）
vector<vector<int>> multiply(const vector<vector<int>> &a, const vector<vector<int>> &b) {
  int n = a.size();
  vector<vector<int>> c(n, vector<int>(n, INT32_MAX / 2));
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      for (int k = 0; k < n; ++k) { c[i][j] = min(c[i][j], a[i][k] + b[k][j]); }
    }
  }
  return c;
}

// 矩阵快速幂
vector<vector<int>> pow(vector<vector<int>> base, int exp) {
  int n = base.size();
  // 零元矩阵: min(a, INT32_MAX / 2) = a
  vector<vector<int>> result(n, vector<int>(n, INT32_MAX / 2));
  for (int i = 0; i < n; ++i) { result[i][i] = 0; }  // 单位元: a + 0 = a
  while (exp > 0) {
    if ((exp & 1) != 0) { result = multiply(result, base); }
    base   = multiply(base, base);
    exp  >>= 1;
  }
  return result;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  using TIII = tuple<int, int, int>;

  int n, t, s, e;
  cin >> n >> t >> s >> e;
  vector<TIII> edges(t);
  map<int, int> point_id;
  for (int i = 0; i < t; ++i) {
    int l, x, y;
    cin >> l >> x >> y;
    if (point_id.count(x) == 0) { point_id[x] = point_id.size(); }
    if (point_id.count(y) == 0) { point_id[y] = point_id.size(); }
    edges[i] = {l, point_id[x], point_id[y]};
  }
  s         = point_id[s];
  e         = point_id[e];
  int m     = point_id.size();

  using VI  = vector<int>;
  using VVI = vector<VI>;

  VVI graph(m, VI(m, INT32_MAX / 2));
  for (const auto &[l, x, y] : edges) { graph[x][y] = graph[y][x] = min(graph[x][y], l); }
  VVI result = pow(graph, n);
  cout << result[s][e] << "\n";
  return 0;
}

不超过 k 步最短路

计算从起点 $s$ 到终点 $t$ 经过不超过 $k$ 条边的最短路径长度，可以通过计算矩阵 $B = A^0 + A^1 + ... + A^k$ 来实现，其中 $A$ 是图的邻接矩阵，矩阵乘法定义为 $(\min, +)$ 代数下的乘法。 $B$ 矩阵的第 $s$ 行第 $t$ 列的值即为所求的最短路径长度。

具体实现可以使用矩阵快速幂结合增广矩阵的方法，将邻接矩阵扩展为一个更大的矩阵，以便在计算幂次时同时考虑路径长度的累积。

构造增广矩阵 $C$ ，其形式如下：

$C = \begin{bmatrix} A & I \\ 0 & I \end{bmatrix}$

其中 $I$ 是单位矩阵， $0$ 是零矩阵。计算 $C^{k+1}$ 后，结果矩阵的右上部分即为 $B = A^0 + A^1 + ... + A^k$ （左上部分是 $A^{k+1}$ ）。

也可以对原图中每个节点 $v$ 拓展出一个虚拟节点 $v'$ ，并添加边 $(v, v')$ 和 $(v', v)$ ，权重均为 $0$ （即每个节点增加一个自环）。这样从节点 $s$ 到节点 $t'$ 的恰好 $k+1$ 条边的最短路径即为从 $s$ 到 $t$ 不超过 $k$ 条边的最短路径。因为原图中的路径可以通过这些自环节点来"停留"，从而实现不超过 $k$ 条边的路径长度。

最短路径⚓︎

Dijkstra 算法⚓︎

分层最短路径⚓︎

Floyd-Warshall 算法⚓︎

Bellman-Ford 算法⚓︎

SPFA 算法⚓︎

Johnson 算法⚓︎

其他最短路径问题⚓︎

经过恰好 k 条边的路径数量⚓︎

定长最短路径⚓︎

评论