单源最短路题目总结

姚军

2487

2021.11.26

2022.03.13

发布于未知归属地

最短路 Dijkstra 算法 Floyd SPFA 技术交流

单源最短路

通常是求从一个起点到其余点的最短距离。所涉及的算法有
1. 朴素版dijkstra $O (n^{2})$
2. 堆优化版dijkstra $O (m l o g n)$ 有重边的优先队列 $O (m l o g m)$
3. floyd $O (n^{3})$
4. bellman-ford $O (nm)$
5. spfa 一般 $O (m)$ 最坏 $O (nm)$
通常根据顶点数 $n$ 或者边数 $m$ 来选择算法，因为spfa一般情况时间复杂度较低，所以我通常用spfa来写题。

最短路常用模板

以743题为例，分别实现了四个版本

朴素版dij
堆优化版dij
floyd
spfa

参考代码：朴素版dij

适用范围：稠密图
点和边在1000左右

class Solution {
public:
    
    using PII = pair<int, int>;
    vector<vector<PII>> g;
    int networkDelayTime(vector<vector<int>>& times, int n, int k) {
        const int INF = 0x3f3f3f3f;
        // build graph
        g.resize(n+1);
        for(auto time: times) {
            int x = time[0], y = time[1], z = time[2];
            g[x].push_back({y, z});
        }
        // dij
        vector<int> d(n+1, INF);
        vector<bool> vis(n);
        d[k] = 0;
       int res = 0;

        for(int i = 1; i <= n; i++) {
            int j = -1;
            // select the vertex with less weight
            for(int u = 1; u <= n; u++) {
                if(!vis[u] && (j == -1 || d[u] < d[j])) j = u;
            }
            if(j == -1) break;
            vis[j] = true;
            // relax distance
            for(const auto& [v, w]: g[j]) {
                    d[v] = min(d[v], d[j] + w);
            }
        }
       
        for(int i = 1; i <= n; i++) res = max(res, d[i]);
        return res >= INF? -1: res;

    }
};

堆优化dij

适用范围：稀疏图，边和点的数据范围在 $1 0^{5}$ 左右

class Solution {
public:
    using PII = pair<int, int>;
    vector<vector<PII>> g;
    int dist[110];
    bool st[110];
    void dij(int start) {
        memset(st, 0, sizeof st);
        memset(dist, 0x3f, sizeof dist);
        priority_queue<PII, vector<PII>, greater<PII>> pq;
        dist[start] = 0;
        pq.push({0, start});

        while(pq.size()) {
            auto [_, u] = pq.top(); pq.pop();
            if(st[u]) continue;
            st[u] = true;

            for(auto [v, w]: g[u]) {
                if(st[v]) continue;
                if(dist[v] > dist[u] + w){
                    dist[v] = dist[u] + w;
                    pq.push({dist[v], v});
                }
            }
        }
    }
    int networkDelayTime(vector<vector<int>>& ts, int n, int k) {
        g.resize(n+1);
        for(int i = 0; i < ts.size(); i++) {
            int x = ts[i][0], y = ts[i][1], z = ts[i][2];
            g[x].push_back({y, z});
        }
        
        dij(k);
        int res = INT_MIN;
        for(int i = 1; i <= n; i++) {
            res = max(res, dist[i]);
        }
        return res == 0x3f3f3f3f?-1: res;
    }
};

参考代码：SPFA版本

适用范围：边权为负
数据范围在 $1 0^{5}$ 左右

class Solution {
public:
    // spfa
    // 使用队列来标记待松弛的点
    // st数组用来标记在队列中的点
    using PII = pair<int, int>;
    vector<vector<PII>> g;
    int dist[110];
    bool st[110];
    void spfa(int start) {
        memset(st, 0, sizeof st);
        memset(dist, 0x3f, sizeof dist);
        queue<int> q;
        dist[start] = 0;
        q.push(start);
        st[start] = true; // 注意，这里是区别
        while(q.size()) {
            auto u = q.front(); q.pop();
            st[u] = false;
            // 更新这个点所有相连的边
            for(auto [v, w]: g[u]) {
                if(dist[v] > dist[u] + w){
                    dist[v] = dist[u] + w;
                    if(st[v]) continue;
                    st[v] = true;
                    q.push(v);
                }
            }
        }
    }
    int networkDelayTime(vector<vector<int>>& ts, int n, int k) {
        g.resize(n+1);
        for(int i = 0; i < ts.size(); i++) {
            int x = ts[i][0], y = ts[i][1], z = ts[i][2];
            g[x].push_back({y, z});
        }
        
        spfa(k);
        int res = INT_MIN;
        for(int i = 1; i <= n; i++) {
            res = max(res, dist[i]);
        }
        return res == 0x3f3f3f3f?-1: res;
    }
};

参考代码：Floyd版本

适用范围：点的数据在200左右

class Solution {
public:
    int networkDelayTime(vector<vector<int>>& times, int n, int k) {
        // build graph
        const int INF = 0x3f3f3f3f;
        vector<vector<int>> g(n+1, vector<int>(n+1, INF));
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= n; j++){
                if(i == j) g[i][j] = 0;
            }
        }
        for(auto t: times) {
            g[t[0]][t[1]] = t[2];
        }
        // floyd
        for(int k = 1; k <= n; k++) {
            for(int i = 1; i <= n; i++) {
                for(int j = 1; j <= n; j++){
                    g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
                }
            }
        }
        int res = 0;
        for(int i = 1; i <= n; i++) {
            res = max(res, g[k][i]);
        }
        if(res==0x3f3f3f3f) return -1;
        return res;
    }
};

单源最短路

相关题目

最短路常用模板

参考代码：朴素版dij

堆优化dij

参考代码：SPFA版本

参考代码：Floyd版本