单源最短路径

约 1145 字 预计阅读 4 分钟 本文访问量 0 数据结构与算法 图论 最短路

单源最短路径（Single-Source Shortest Path，SSSP）问题，即给定一个图，求从单一起点到任意给定终点的最短路径

单位权图

即各个边的权重均为 1，此时只要使用 BFS 即可

void bfs(int start) {
    queue<int> q;
    q.push(start);
    dist[start] = 0; // 起点距离为 0
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int v : adj[u]) {
            if (dist[v] == -1) {  // 未访问过才更新！
                dist[v] = dist[u] + 1;
                q.push(v);
            }
        }
    }
}

这个代码对无向图和有向图均可适用

最终 dist 数组中存储的就是从 start 到各个节点的最短路径长度

如果想要得到路径可以再使用一个 parent 前驱数组来记录，最终使用回溯再反转得到

void bfs(int start) {
    queue<int> q;
    q.push(start);
    dist[start] = 0;
    parent[start] = -1; // 起点无前驱，设为 -1
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int v : adj[u]) {
            if (dist[v] == -1) {
                dist[v] = dist[u] + 1;
                parent[v] = u; // 记录v的前驱是u
                q.push(v);
            }
        }
    }
}

vector<int> get_shortest_path(int start, int end) {
    vector<int> path;

    if (dist[end] == -1) {
        return path;  // 不可达，返回空路径
    }
    for (int cur = end; cur != -1; cur = parent[cur]) {
        path.push_back(cur); // 从 end 回溯到 start
    }
    reverse(path.begin(), path.end()); // 反转得到正序
    return path;
}

一道不完全是但有点相关的题目

正权图

权重的引入需要新的数据结构进行存储，这里可以修改邻接表，将边的信息从 v 改为 pair<int, int>，其中第一个元素为 v，第二个元素为 w，表示从 u 到 v 的权重为 w

typedef pair<int, int> pii; // 简化

vector adj(n+1, vector<pii>());

cin >> u >> v >> w;
adj[u].emplace_back(v,w);

当引入权重之后，BFS 就不再适用了，而当权重为正时可以使用 Dijkstra 算法

Dijkstra 算法

Dijkstra 算法的基本思想是贪心，每次选择当前距离源点最近且未被访问的顶点，以该顶点为中介更新其邻接顶点到源点的距离，重复此过程直到所有顶点都被访问

模板题链接

朴素 Dijkstra

void native_dijkstra(const vector<vector<pii>> &adj, vector<int> &dist)
{
    // fill(dist.begin(), dist.end(), INF); // 或保证外部实现
    dist[start] = 0;
    vector visited(n+1, false);
    for (int i = 0; i < n; i++)
    {
        int u = -1; // 寻未访问且距离最小者
        for (int j = 1; j <= n; j++)
        {
            if (!visited[j] && (u == -1 || dist[j] < dist[u]))
            {
                u = j;
            }
        }
        if (u == -1 || dist[u] == INF) break; // 找不到点或剩下的点均不可达
        visited[u] = true;
        for (const auto [v, w] : adj[u])
        {
            if (!visited[v] && dist[v] > dist[u] + w)
            {
                dist[v] = dist[u] + w;
            }
        }
    }
}
  • 时间复杂度：\(O(n^2)\)

堆优化 Dijkstra

当然，找最小距离这一步可以使用小根堆进行优化

void dijkstra(const vector<vector<pii>> &adj, vector<int> &dist)
{
    // fill(dist.begin(), dist.end(), INF);
    // 权重，节点
    priority_queue<pii, vector<pii>, greater<>> pq;
    pq.emplace(0,start);
    dist[start] = 0;

    while (!pq.empty())
    {
        auto [curW, u] = pq.top();
        pq.pop();

        // 剪枝：跳过旧数据
        if (curW > dist[u]) continue;

        for (const auto [v, w] : adj[u])
        {
            if (dist[v] > dist[u] + w) // 松弛
            {
                dist[v] = dist[u] + w;
                pq.emplace(dist[v], v);
            }
        }
    }
}
  • 时间复杂度：\(O((n+m)\log n)\)

朴素 VS 堆优化

即 \(O(n^2)\) VS \(O((n+m)\log n)\)，其中 \(m\) 为边数

  • 当图为稠密图时，即 \(m\) 接近 \(n^2\)，朴素算法更优，少了一个 \(\log n\)
  • 当图为稀疏图时，即 \(m\) 远小于 \(n^2\)，堆优化更优

既然都稠密图了，一般用邻接矩阵了

void native_dijkstra(const vector<vector<int>> &adj, vector<int> &dist)
{
    // fill(dist.begin(), dist.end(), INF); 
    dist[s] = 0;
    vector visited(n+1, false);
    for (int i = 0; i < n; i++)
    {
        int u = -1; // 寻未访问且距离最小者
        for (int j = 1; j <= n; j++)
        {
            if (!visited[j] && (u == -1 || dist[j] < dist[u]))
            {
                u = j;
            }
        }
        if (u == -1 || dist[u] == INF) break; // 找不到点或剩下的点均不可达
        visited[u] = true;
        for (int v = 1; v <= n; v++)
        {
            // 用邻接矩阵需要特别判断是否可达 adj[u][v] != INF
            if (!visited[v] && adj[u][v] != INF && dist[v] > dist[u] + adj[u][v])
            {
                dist[v] = dist[u] + adj[u][v];
            }
        }
    }
}

无向图和有向图都可以用 Dijkstra 算法

负权图

当边的权重存在为负时，Dijkstra 算法将不再适用，因为该算法通过不断扩大 “已知最短路径节点” 的集合来工作

在负权图中一般默认有向，否则只要有一条边为负权，就存在负权环，此时无法确定最短路径

Bellman-Ford 算法

在一个没有负权环的图中，任意两点间的最短路径不可能包含回路。因此，一条最短路径最多包含 \(n\) 个顶点，即最多包含 \(n-1\) 条边

重复 “对所有边进行松弛” 这一操作 \(n-1\) 次，足以覆盖所有可能的最短路径：第 1 轮循环结束后，算法保证找到了所有“从源点出发，最多经过 1 条边”能到达的节点的最短路径。第 \(k\) 轮循环结束后，保证找到了 “最多经过 \(k\) 条边” 的最短路径

另外的，Bellman-Ford 的核心操作是 “遍历所有边”，而邻接表的设计目标是 “按顶点快速找其关联的边”，两者的需求不匹配，故实现上一般直接使用边列表

模板题链接

constexpr long long INF = 1e18; // 不到顶可以防止溢出
struct Edge { int u, v, w; };
int n, m, s;

bool bellman_ford(const vector<Edge>& edges, vector<long long>& dist)
{
    // fill(dist.begin(), dist.end(), INF); 
    dist[s] = 0;

    // 重复 n-1 次松弛操作
    for (int i = 0; i < n - 1; i++)
    {
        bool any_update = false; // 如果一轮中没有任何更新，可以提前结束
        for (const auto& [u, v, w] : edges)
        {
            // 如果 u 可达且通过 u 到 v 更近
            if (dist[u] != INF && dist[v] > dist[u] + w)
            {
                dist[v] = dist[u] + w;
                any_update = true;
            }
        }
        if (!any_update) break;
    }

    // 如果在 n-1 轮之后还能进行松弛，说明存在负权环
    for (const auto& [u, v, w] : edges)
    {
        if (dist[u] != INF && dist[v] > dist[u] + w)
        {
            return false; // 存在负权环
        }
    }
    return true;
}
  • 时间复杂度：\(O(n(m+n))\)

SPFA 算法*

SPFA (Shortest Path Faster Algorithm) 算法是对 Bellman-Ford 算法的优化，标准的 Bellman-Ford 每一轮都盲目地遍历所有边。但实际上，只有 “起点的距离刚刚被更新过” 的边，才有可能引起终点距离的更新。SPFA 使用一个队列来只处理这些 “值得处理” 的节点，从而大幅减少无效计算

void spfa(vector<vector<pair<int, int>>>& adj, vector<long long>& dist)
{
    // fill(dist.begin(), dist.end(), INF); 
    dist[s] = 0;
    queue<int> q;
    q.push(s);
    vector in_queue(n + 1, false); // 标记是否在队列里
    in_queue[s] = true;

    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        in_queue[u] = false;
        // 核心：只遍历 u 的出边，这依然是松弛操作
        for (const auto& [v, w] : adj[u])
        {
            if (dist[v] > dist[u] + w)
            {
                dist[v] = dist[u] + w;
                if (!in_queue[v]) // 避免重复处理
                {
                    q.push(v);
                    in_queue[v] = true;
                }
            }
        }
    }
}
  • 时间复杂度：
    • 平均 \(O(km)\)，其中 \(k\) 是常数，通常在 2 到 3 之间
    • 最坏 \(O(nm)\)

SPFA 同样可以判断有无负环：维护一个数组 cnt[x]，表示从源点到节点 x 的最短路径当前包含的边数

  • 初始化：整个 cnt 数组为 0
  • 更新逻辑：当发生松弛操作 dist[v] > dist[u] + w 时，同时更新 cnt[v] = cnt[u] + 1
  • 判定条件：如果某个时刻 cnt[v] >= n，说明路径上至少有 \(n+1\) 个点，根据抽屉原理，必然存在重复节点（即存在环），返回 true（发现负环）
bool spfa(vector<vector<pair<int, int>>>& adj, vector<long long>& dist)
{
    // fill(dist.begin(), dist.end(), INF);
    queue<int> q;
    vector in_queue(n + 1, false); // 标记是否在队列里
    vector cnt(n + 1, 0); // 最短路上的边数

    // 场景 A：只判断从 s 出发能否到达负环（标准最短路）
    dist[s] = 0;
    q.push(s);
    in_queue[s] = true;

    // 场景 B：判断全图是否存在负环（无论是否连通）
    /* for (int i = 1; i <= n; i++) {
        dist[i] = 0;
        q.push(i);
        in_queue[i] = true;
    }*/

    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        in_queue[u] = false;

        for (const auto& [v, w] : adj[u])
        {
            if (dist[v] > dist[u] + w)
            {
                dist[v] = dist[u] + w;
                cnt[v] = cnt[u] + 1;
                if (cnt[v] >= n) return false;

                if (!in_queue[v]) // 避免重复处理
                {
                    q.push(v);
                    in_queue[v] = true;
                }
            }
        }
    }
    return true;
}

虽然 SPFA 在随机图上表现很好，但在精心构造的网格图或菊花图上，SPFA 的复杂度会退化成 \(O(nm)\)，和朴素 Bellman-Ford 一样慢

建议： 只要没有负权边，永远优先用 Dijkstra。只有在必须处理负权边或判负环时，才用 SPFA

特例：有向无环负权图

在 DAG 中，每条路径，也就是每条最短路径，都是拓扑序中的子序列，故可以按照拓扑序进行动态规划

最短路题目没找到，最长路倒是有。也很自然地想到，从最短路到最长路只需将初始化 INF 改从 -INF，松弛操作的判断符号改变（即取 max）即可

拓扑排序 + 动态规划

void DAGSSSP(int s, vector<int> in, vector<int> &dist, vector<vector<tuple<int,int>>> &adj)
{
    dist[s] = 0; // 只有起点的距离设置为 0
    queue<int> q;
    for (int i = 0; i < n; i++)
    {
        if (in[i] == 0)
        {
            q.push(i);
        }
    }
    while (!q.empty())
    {
        const auto u = q.front(); q.pop();
        for (auto [v ,w] : adj[u])
        {
            if (dist[u] != INF && dist[v] > dist[u] + w)
            {
                dist[v] = dist[u] + w;
            }
            if (--in[v] == 0) q.push(v);
        }
    }
}

btw，判断负环也可使用拓扑排序，若最终有入度不为 0 的节点则存在负环

  • 时间复杂度：\(O(n+m)\)

其他

最短路计数

拓扑判环

缩点：Tarjan + topoSort + DP

标题：单源最短路径

作者：Zwing

创建于：2025-12-01 08:20:25

更新于：2026-08-07 16:17:52

链接：https://zanytriumph.github.io/posts/单源最短路径.html

版权声明：本文章采用 CC BY-NC-SA 4.0 进行许可