a Blog
0%

图最短路径算法

发表于 更新于 分类于 Valine：
本文字数： 3.6k 阅读时长 ≈ 3 分钟

1. Floyd 算法

功能：计算任意两点间的最短路径，适合稠密图。

参数：

  • times：二维数组，每个元素 [u, v, w] 表示从 u 到 v 的边权为 w。
  • n：节点数。
  • m：起点编号。

返回值：起点 m 到所有点的最远距离，若不可达返回 -1。

代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int Floyd(vector<vector<int>> &times, int n, int m) {
  vector<vector<int>> adjacent_matrix(n, vector<int>(n, INT_MAX / 2));
  for (const auto &time : times) {
    adjacent_matrix[time[0]][time[1]] = time[2];
  }

  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
      for (int k = 0; k < n; k++)
        if (adjacent_matrix[j][i] != INT_MAX / 2 && adjacent_matrix[i][k] != INT_MAX / 2)
          adjacent_matrix[j][k] = min(adjacent_matrix[j][k], adjacent_matrix[j][i] + adjacent_matrix[i][k]);

  int max_res = *max_element(adjacent_matrix[m].begin(), adjacent_matrix[m].end());
  return max_res == INT_MAX / 2 ? -1 : max_res;
}

解析：

  • 核心思想：动态规划，依次尝试每个节点作为中间节点更新最短路径。
  • 优点：能处理任意两点间最短路径，逻辑清晰。
  • 缺点：时间复杂度 O(n3)O(n^3)，大图不适合。

2. Dijkstra 算法（优先队列优化）

功能：单源最短路径，适合边权非负稀疏图。

参数：

  • times：边集合。
  • n：节点数。
  • k：起点编号。

返回值：起点 k 到所有点的最远距离，若不可达返回 -1。

代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
int Dijkstra_priority(vector<vector<int>> &times, int n, int k) {
  vector<int> he(n, -1), e(times.size()), ne(times.size()), w(times.size());
  for (int i = 0; i < times.size(); i++) {
    e[i] = times[i][1];
    w[i] = times[i][2];
    ne[i] = he[times[i][0]];
    he[times[i][0]] = i;
  }
  vector<int> dis(n, INT_MAX / 2);
  priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
  dis[k] = 0;
  pq.push({0, k});
  vector<bool> visited(n, false);

  while (!pq.empty()) {
    auto [step, id] = pq.top(); pq.pop();
    if (visited[id]) continue;
    visited[id] = true;

    for (int j = he[id]; j != -1; j = ne[j]) {
      int dst = e[j];
      if (dis[dst] > dis[id] + w[j]) {
        dis[dst] = dis[id] + w[j];
        pq.push({dis[dst], dst});
      }
    }
  }

  int max_res = *max_element(dis.begin(), dis.end());
  return max_res == INT_MAX / 2 ? -1 : max_res;
}

解析：

  • 核心思想：贪心 + 最小堆，优先扩展距离最短的节点。
  • 优点：时间复杂度 O(Elog⁡V)O(E \log V)，适合稀疏图。
  • 缺点：无法处理负权边。

3. Bellman-Ford 算法

功能：单源最短路径，可处理负权边。

代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int Bellman_Ford(vector<vector<int>> &times, int n, int k) {
  vector<int> dis(n, INT_MAX / 2);
  dis[k] = 0;
  bool updated = false;

  for (int i = 0; i < n; i++) {
    updated = false;
    for (auto time : times) {
      int u = time[0], v = time[1], w = time[2];
      if (dis[u] != INT_MAX / 2 && dis[u] + w < dis[v]) {
        dis[v] = dis[u] + w;
        updated = true;
      }
    }
    if (!updated) break;
  }

  if (updated) return -1; // 负环
  int max_res = *max_element(dis.begin(), dis.end());
  return max_res == INT_MAX / 2 ? -1 : max_res;
}

解析：

  • 核心思想：松弛操作迭代 n-1 次，确保最短路径更新到最优。
  • 优点：可处理负权边，逻辑简单。
  • 缺点：时间复杂度 O(VE)O(VE)，图大时慢；检测负环。

4. SPFA（Bellman-Ford 队列优化）

功能：Bellman-Ford 优化版，用队列减少冗余松弛。

代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
int Spfa(vector<vector<int>> &times, int n, int k) {
  vector<int> he(n, -1), e(times.size()), ne(times.size()), w(times.size());
  for (int i = 0; i < times.size(); i++) {
    e[i] = times[i][1];
    w[i] = times[i][2];
    ne[i] = he[times[i][0]];
    he[times[i][0]] = i;
  }

  vector<int> cnt(n, 0), dis(n, INT_MAX / 2);
  vector<bool> visited(n, false);
  dis[k] = 0;
  queue<int> q;
  q.push(k);
  visited[k] = true;

  while (!q.empty()) {
    int i = q.front(); q.pop();
    visited[i] = false;
    for (int j = he[i]; j != -1; j = ne[j]) {
      int dst = e[j];
      if (dis[i] != INT_MAX / 2 && dis[dst] > dis[i] + w[j]) {
        dis[dst] = dis[i] + w[j];
        if (!visited[dst]) {
          q.push(dst);
          visited[dst] = true;
          if (++cnt[dst] > n) return -1; // 负环
        }
      }
    }
  }

  int max_res = *max_element(dis.begin(), dis.end());
  return max_res == INT_MAX / 2 ? -1 : max_res;
}

解析：

  • 核心思想：队列优化，避免无效松弛。
  • 优点：平均复杂度比 Bellman-Ford 更低，适合稀疏图。
  • 缺点：仍无法保证最坏情况性能，仍需检测负环。

方法对比

方法 时间复杂度 适用场景 是否支持负权 备注
Floyd O(n³) 稠密图 否 任意两点最短路径，简单直观
Dijkstra（优先队列） O(E log V) 稀疏图，边权非负 否 单源最短路径，高效
Bellman-Ford O(VE) 可含负权边图 是 能检测负环
SPFA 平均 O(E) 稀疏图，可含负权 是 Bellman-Ford 队列优化版