题解 | #单源最短路#

题目：单源最短路径
描述：在一个有向无环图中，已知每条边长，求出1到n的最短路径，返回1到n的最短路径值。如果1无法到n，输出-1
示例1：输入：5,5,[[1,2,2],[1,4,5],[2,3,3],[3,5,4],[4,5,5]]，返回值：9
备注：两个整数n和m,表示图的顶点数和边数。
一个二维数组，一维3个数据，表示顶点到另外一个顶点的边长度是多少
每条边的长度范围[0,1000]。注意数据中可能有重边

解法一：
思路分析：首先我们理解题目，题目的意思是求解单源最短路径，在一个有向无环图中，已知了边长，要求求解1到n的最短路径值，当1到不了n时，就返回-1。
——题目中有一个示例，我们进行分析，首先规定了图的顶点数和边数分别为5和5，下面我们给出该有向无环图：
图片说明
——从图中，我们可以清楚的看到从1到5有两条路径可选，一条为{1，2，3，5}，路径的权值和为2 + 3 + 4 = 9，另一条为{1，4，5}，路径的权值和为10，所以单源最短路径为9，最后返回值也为9。
——既然知道了题目的含义，同时应该明白单源最短路径的求解方法有一个是迪杰斯特拉算法(Dijkstra)，对于迪杰斯特拉算法，它是一种典型的求解最短路径的算法，它可以很方便的计算从一个结点到其他结点的最短路径，其主要是以起点为中心向外层层层扩展，直到扩展到终点，便结束，运用的是广度优先搜索遍历的思想，在该算法中首先我们需要指定一个起点，就是从起点开始计算，其次需要记录求出最短路径的顶点以及相应的最短路径长度，还需要记录未求出的最短路径的顶点，最后在存储的内存空间中我们需要实时更新最短路径长度和顶点的信息，方便进行最后的计算。重复操作，一直到遍历完所有的顶点便结束操作，Dijkstra算法是基于贪心策略的算法，如果在矩阵中存在负的权值问题，那么该算法并不适用。
实例分析：我们使用Dijkstra算法对实例1进行分析：
图片说明
C++核心代码为：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int 顶点数
     * @param m int 边数
     * @param graph intvector<vector<>> 一维3个数据，表示顶点到另外一个顶点的边长度是多少
     * @return int
     */
    using PII = pair<int, int>;//存储两个相同类型的值
    const int INF = 0x3f3f3f3f;//32-bit int的最大值
    int findShortestPath(int n, int m, vector<vector<int> >& graph) {
        // write code here
        vector<vector<PII>> tab(n + 1);
        for(const auto& i : graph)
            tab[i[0]].emplace_back(i[1],i[2]);//和push_back大体相同
        return dijal(tab,n);
    }

    int dijal(vector<vector<PII>>& tab,int n){
        vector<int> pon(n + 1,0);
        vector<int> lin(n + 1,INF);
        lin[1] = 0;
        priority_queue<PII, vector<PII>, greater<PII>> q;//创建一个优先队列
        q.emplace(0,1);//在0位置插入1
        while (not q.empty()){
            const auto  [dist, cur] = q.top(); q.pop();

      if (pon[cur]++) continue;

      for (const auto [nxt, w] : tab[cur])
        if (dist + w < lin[nxt]) {
          lin[nxt] = dist + w;
          q.emplace(dist + w, nxt);
        }
    }

    return lin[n] == INF ? -1 : lin[n];
    }
};

——因为是采用的Dijkstra算法，首先将graph数组中的元素存入tab中，然后创建一个优先队列进行初始化定义，循环tab中点和边，最终输出，所以其时间复杂度为 $O(N^2)$ )，因为定义了一个容器对象tab和一个优先队列q用于存储点和边，所以其空间复杂度为 $O(N)$ 。