题解 | #单源最短路#

NC158 单源最短路

单源最短路是图论算法里非常重要的基础算法，似乎没有之一。。。。。。

常用的算法有dijkstra算法和SPFA算法，下面分别介绍。

题意

给你一个有向图，n点m边，有重边无自环，权值为正，求 1 到 n 的最短路，如果不存在，输出-1.

1. 迪杰斯特拉

这个似乎是数据结构课的新人杀手了。。。。

dijkstra算法的流程如下：

• 初始化dist[1]=0,其他为inf，令s集合表示已经确定最短距离的点
• 遍历n次：

1. 寻找不在s中的，距离s集合最近的点t
2. vis[t]=true, 即加入s中
3. 遍历s中的所有点，对每个点j更新dist[j]=min(dist[j],dist[t]+f[t][j]) ，实际这一步可以遍历全部点，因为dij算法不支持负边，无穷大加正数还是无穷大。

这样做，时间复杂度会达到，因为有两重的遍历，通常的题目是稀疏图（例如边数1e6），且点数达到1e5，肯定是不行的。

上述过程中的第3步，我们发现，加入t之后，用t更新s中的所有点是一个线性遍历的过程，但是，我们可以不用线性扫点，而是直接挑选距离S最近的点进行更新，所以可以维护一个小根堆，每次从堆顶取的就是不在S中距离起点最近的那个。

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int 顶点数
     * @param m int 边数
     * @param graph intvector<vector<>> 一维3个数据，表示顶点到另外一个顶点的边长度是多少​
     * @return int
     */
    using pii = pair<int, int>;
    // 定义小根堆，存储当前距离1号点的距离和下标
    // 默认的priority_queue是大根堆，要特殊定义一下，这样写是固定写法。
    // stl中，pair的比较是先比第一个，再比第二个，所以距离要放前面
    using minheap = priority_queue<pii,vector<pii>,greater<pii> >;

    static const int N = 210, M = 510; // 本题大约的数据范围是200个点，500个边。
    // 定义初始距离为无穷大, 这个数约为1e9，够大，且相加不爆int，相乘不爆ll，是算法题中常见的无穷大定义
    static const int INF = 0x3f3f3f3f; 

    // 前向星存储
    struct Edge {
        int to, next, dis;
    } e[M];

    int head[N], dist[N], idx = 1;
    bool vis[N];

    void add(int a, int b, int c) {
        e[idx].to = b;
        e[idx].next = head[a];
        e[idx].dis = c;

        head[a] = idx++;
    }

    void dijkstra(int start) {
        memset(dist, 0x3f, sizeof dist);
        dist[start] = 0;

        minheap h;
        h.push({0, start}); //先把起点放进去

        while (!h.empty()) {
            // 找到不在S中，距离起点最近的那个
            int u = h.top().second;
            h.pop();

            if (!vis[u]) {
                // 加入S中
                vis[u] = true;
                // 遍历出边
                for (int i = head[u]; ~i; i = e[i].next) {
                    int j = e[i].to;
                    // 如果可以更新，就放进小根堆
                    if (dist[j] > dist[u] + e[i].dis) {
                        dist[j] = dist[u] + e[i].dis;
                        h.push({dist[j], j});
                    }
                }
            }
        }
    }

    int findShortestPath(int n, int m, vector<vector<int> >& graph) {
        memset(head, -1, sizeof head);
        memset(vis, 0, sizeof vis);
        for (auto g : graph) {
            add(g[0], g[1], g[2]);
        }

        dijkstra(1);

        if (dist[n] == INF) return -1;
        return dist[n];
    }
};

• 时间复杂度：, 宽搜部分按边遍历，堆中存的是点，入堆过程的复杂度是.
• 空间复杂度：. 堆中最多存了整个图的全部点。

2. spfa

方法一虽然经典，但是不支持负权边。下面介绍一种支持负权边的算法————SPFA(Shortest Path Faster Algorithm)算法。

算法流程如下：

• 维护一个队列，初始时加入起点
• 每次迭代，取出队头的点v，依次枚举从v出发的边v->u，设边的长度为len，判断dist[v]+len是否小于dist[u]，若小于则缩小dist[u]（这个操作叫松弛）
• 如果u没有访问过，则u入队
• 直到队列为空。

以样例为例，图解算法流程如下：

• 初始状态队列中为1，dist[i]=0, 其他为inf
• 1出队，2，4入队，更新dist[2]=2, dist[4]=5
• 2，4出队，3，5入队，更新dist[3]=5, dist[5]=10
• 3出队，更新dist[5]=9
• 5出队，队列为空

class Solution {
public:
    static const int N = 210, M = 510; // 本题大约的数据范围是200个点，500个边。
    static const int INF = 0x3f3f3f3f; // 定义初始距离为无穷大

    struct Edge {
        int to, next, dis; // 存储图
    } e[M];

    int head[N], dist[N], idx = 1;
    bool vis[N];

    void add(int a, int b, int c) {
        e[idx].to = b;
        e[idx].next = head[a];
        e[idx].dis = c;

        head[a] = idx++;
    }

    void spfa(int start) {
        memset(dist, 0x3f, sizeof dist);
        dist[start] = 0;

        queue<int> q;
        q.push(start);

        vis[start] = true; //判重数组， 队列中有重复的点没有意义

        while (q.size()) {
            int t = q.front();
            q.pop();

            vis[t] = false;

            // 遍历队头的点t的所有出边
            for (int i = head[t]; ~i; i = e[i].next) {
                int j = e[i].to; // t->j的有向边
                // 松弛操作j点
                if (dist[j] > dist[t] + e[i].dis) {
                    dist[j] = dist[t] + e[i].dis;
                    // 如果j没入队过，把j加入队列
                    if (!vis[j]) {
                        q.push(j);
                        vis[j] = true;
                    }
                }
            }
        }
    }

    int findShortestPath(int n, int m, vector<vector<int> >& graph) {
        memset(head, -1, sizeof head);
        memset(vis, 0, sizeof vis);
        // 邻接矩阵转换成链表形式存图
        for (auto g : graph) {
            add(g[0], g[1], g[2]);
        }

        spfa(1);

        if (dist[n] == INF) return -1; // 如果没有更新到n点，说明不存在最短路径
        return dist[n];
    }
};

• 时间复杂度：通常认为是, m是边数，k是较大的常数，在特殊的数据下，最坏为, 其中n是点数。
• 空间复杂度：. 定义了长度为点数的队列。

3. 总结

选择算法时，需要注意：

• 如果有负权边，必须使用spfa
• 如果没有负权边，对稀疏图建议使用前向星存储+堆优化dijkstra，对稠密图（边数是点数平方级别）的话，如果用堆优化版本，时间复杂度就变成了, 反而劣于普通dij。因此稠密图建议用邻接矩阵存储的dij。当然，用spfa也可以，但记住这玩意在笔试中，如果题目条件给出边权为正，很可能会被出题人故意构造数据卡掉！
• 如果有负环，则最短路是负无穷大，判断方法是在spfa里增加一个数组记录下每个点的最短路被更新过几次，如果超过了n次，说明走到这个点的路径长度超过n了，这就证明在转圈，所以存在负环。