最短路径算法

概念讲解

算法对比

算法 时间复杂度 适用条件
Dijkstra O(m log n) 非负权边
SPFA O(km) 可判负环
Floyd O(n³) 任意图

Dijkstra

思路

贪心：每次选距离最小的未访问节点，更新邻居距离。

代码（堆优化）

12345678910111213141516171819202122232425const int N = 100005;
vector<pair<int,int>> graph[N];  // {v, w}
int dist[N];
bool visited[N];

void dijkstra(int start) {
    memset(dist, 0x3f, sizeof(dist));
    dist[start] = 0;
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;
    pq.push({0, start});
    
    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();
        if (visited[u]) continue;
        visited[u] = true;
        
        for (auto& [v, w] : graph[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
}

SPFA

1234567891011121314151617181920212223void spfa(int start) {
    memset(dist, 0x3f, sizeof(dist));
    dist[start] = 0;
    queue<int> q;
    q.push(start);
    inQueue[start] = true;
    
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        inQueue[u] = false;
        
        for (auto& [v, w] : graph[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                if (!inQueue[v]) {
                    q.push(v);
                    inQueue[v] = true;
                }
            }
        }
    }
}

Floyd

1234567891011int dist[N][N];

void floyd(int n) {
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    }
}

考点分析

初赛考查方式

  1. 程序阅读： 最短路径程序
  2. 编程题： 最短路径应用

常见考点

  • Dijkstra 算法
  • SPFA 判负环
  • Floyd 多源最短路

例题精讲

例题 1：Dijkstra

题目： 求单源最短路径。

解答：

使用 Dijkstra 算法，时间复杂度 O(m log n)。

练习题

  1. Dijkstra 不能处理什么情况？
查看答案

Dijkstra 不能处理负权边。

因为 Dijkstra 基于贪心思想，每次选择距离最小的未访问节点。如果有负权边，可能导致已确定的最短路径被更新，破坏贪心的正确性。

  1. SPFA 的时间复杂度是多少？
查看答案
  • 平均时间复杂度：O(km)O(km)，k 是常数（通常 k ≤ 2）
  • 最坏时间复杂度：O(nm)O(nm)

SPFA 可以判断负环：如果某个节点入队超过 n 次，则存在负环。

  1. Floyd 适用于什么场景？
查看答案

Floyd 适用于多源最短路问题：

  • 求所有节点对之间的最短距离
  • 时间复杂度：O(n3)O(n^3)
  • 空间复杂度：O(n2)O(n^2)
  • 适用于稠密图（边数接近 n2n^2）
  • 可以处理负权边（但不能有负环）

易错点

⚠️ 注意：

  1. Dijkstra 不能处理负权边
  2. SPFA 最坏 O(nm)
  3. Floyd 要 k 在最外层
  4. 初始化 dist 为 INF