NC158 题解 | #单源最短路#

题意分析

给出一张有向图，需要我们计算出从1号结点到达n号结点的最短的距离。

大意分析

这个是一个很明显的一个模板题，相信大家在数据结构课程上都学过，现在就让我们来温习一遍。这个其实也可以理解为一种贪心的思想吧。我们从一号结点开始进行拓展，先找到离1号结点最短距离同时没有被访问过的点。然后我们进行扩展，我们不断更新从1号结点到达每个结点的最短的距离，这样，我们可以很容易证明，我们最多只需要扩展n次就可以得到我们最后想要的结果。因为我们在寻找没有访问过的点的时候，最多就是遍历n个结点，而且，我们从一号结点到达n号结点最多也只需要n-1步到达。
接下来，我们来大致的讲解一下什么是Dijkstra算法。
- 这种算法是为了解决最短路径中的一种问题——在一个有向图中，从某一个固定的点出发，然后求到达每个结点的最短的路径的距离。
- 一开始对于这类问题的思路是可不可以用一个记忆化的搜索进行暴力搜索，然后遍历到当前结点的时候进行更新为最小值。但是似乎如果数据量比较大的时候复杂度有点大。下面就来介绍一下Dijkstra算法基本思想，就是从最初规定的出发的那个点开始进行传递，然后先假设最初点s到其余所有的点距离为无穷大，然后逐层更新每个点的最短路径。我们以下图为例（红色代表起始结点，黑色数字表示的是结点编号，蓝色数字表示边权）：
- 我们标注为红色的就是我们的起始点，然后，我们依次开放可以从1直接到达的那些点，我们可以看到，从1可以直接到达2，5，距离分别为5，6。那么我们选取前已知的最短的距离，也就是到2的距离，然后d[2]=5，接下来，我们开放从2可以直接到达的那些点，我们可以知道，从2只可以到达5，则目前已知的距离和还未真正确定的距离就是从1到5这一个点的距离了，我们知道最短为6，那么就令d[5]=6,接着，开放从5可以直接到的那些点的。我们发现就只有4号点（图中忘记标那个点的位置了，就是最左边的那个点），所以，我们接着更新4号结点的d[4]，最后同理更新3号结点d[3]。
该算法的基本思路大概就是这样的，想要证明可以去《算法导论》中找，个人觉得，这种算法可以这样理解，就是我最初是更新可以从起始点直接到的那些点的最短距离，然后我开放我已经确定好的最短距离的那些点的去向，然后接着更新，这样下来，我其实就是逐步求到了最优解，然后从局部更新到整体，这样就确保了我最后求下来的就是最短距离了，这个其实和我们的动态规划（DP）的思想是类似的。当然，这只是我自己的一点见解，具体还是建议去看看算法笔记。

解法一贪心拓展

按照上面的思路，我们从1号结点开始不断向外进行扩展，然后不断更新我们每个点到1号结点的距离，更新了n-1次之后，我们就得到了1号结点到n号结点的最短的距离了。
代码如下
- 外层循环n-1次，作为扩展的次数，对于每次扩展，需要更新n个点到1号结点的最短距离，所以总的时间复杂度为 $O (n^{2})$
- 在过程中，我们需要用vis数组存储每个结点的情况，用d数组存储每个结点到1号结点的最短的距离，同时用了a数组存储任意两个结点之间的连边的长度，所以总的空间复杂度为 $O (n^{2})$

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int 顶点数
     * @param m int 边数
     * @param graph intvector<vector<>> 一维3个数据，表示顶点到另外一个顶点的边长度是多少
     * @return int
     */
    const int INF=1e9;
    int a[505][505];
    int d[505];
    bool vis[505];
    void Dijkstra(int n){
        memset(d,0x3f,sizeof(d));
        memset(vis,false,sizeof(vis));
        d[1]=0;
        // 拓展每一个点，一共需要拓展n次
        for(int i=1;i<n;i++){
            int x=0;
            // 首先，我们找到第一个没有被访问的，同时距离1号结点最近的一个点的位置
            for(int j=1;j<=n;j++){
               if(!vis[j]&&(x==0||d[j]<d[x])) x=j;
            }
            // 将这个点标记为访问过
            vis[x]=true;
            // 然后不断更新其余的点距离1号结点的距离
            for(int y=1;y<=n;y++){
                d[y]=min(d[y],d[x]+a[x][y]);
            }
        }
    }
    int findShortestPath(int n, int m, vector<vector<int> >& graph) {
        // write code here
        memset(a,0x3f,sizeof(a));
        // 连边，建图
        for(auto x:graph) {
            a[x[0]][x[1]]=min(a[x[0]][x[1]],x[2]);
        }
        Dijkstra(n);
        return d[n]==0x3f3f3f3f?-1:d[n];
    }
};

解法二大根堆优化

还是按照上面的那种思路，我们发现可以进一步优化，我们发现，对于每次处理完之后的点，我们没有必要继续进行访问了，我们只需要遍历处理那些没有访问过的点，同时为了维护边权最小的在堆顶上面，我们对每个权取反操作，然后我们用大根堆进行维护，其实也就相当于是小根堆了。这样，我们只需要扩展 $n l o g n$ 次即可。
代码如下
- 利用大根堆(优先队列)进行优化，总的时间复杂度为 $O (n l o g n)$
- 在过程中，我们需要用vis数组存储每个结点的情况，用d数组存储每个结点到1号结点的最短的距离，同时用了a数组存储任意两个结点之间的连边的长度，所以总的空间复杂度为 $O (n^{2})$

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int 顶点数
     * @param m int 边数
     * @param graph intvector<vector<>> 一维3个数据，表示顶点到另外一个顶点的边长度是多少
     * @return int
     */
    vector<pair<int,int> > v[505];
    int d[505];
    bool vis[505];
    priority_queue<pair<int,int> >q; // 我们定义一个大根堆，将路径的权值负数存储，这样权值小的，负数就大，所以在上面
    void Dijkstra(int n){
        memset(d,0x3f,sizeof(d));
        memset(vis,false,sizeof(vis));
        d[1]=0;
        q.push(make_pair(0,1));
        while(!q.empty()){
            int x=q.top().second;
            q.pop();
            // 找到相关联的点，更新到这些结点的长度
            for(auto k:v[x]){
                int y=k.first,z=k.second;
                // 如果通过这个x点，到达y点的距离更短，那么进行更新的操作
                if(d[y]>d[x]+z){
                    d[y]=d[x]+z;
                    q.push(make_pair(-d[y],y));
                }
            }
        }
    }
    int findShortestPath(int n, int m, vector<vector<int> >& graph) {
        // write code here
        // 建图
        for(auto x:graph){
            v[x[0]].push_back(make_pair(x[1],x[2]));
        }
        Dijkstra(n);
        return d[n]==0x3f3f3f3f?-1:d[n];
    }
};

NC158 题解 | #单源最短路#

NC158 题解 | #单源最短路#

题意分析

大意分析

解法一 贪心拓展

解法二 大根堆优化

解法一贪心拓展

解法二大根堆优化