• 设置源节点为$v$，其他节点均设置两个数组，分别为$d[i]$表示从源节点到该节点的最短权值，$vist[i]$表示该节点是否被访问过，若$vist[i]=0$，表示未被访问过
• 初始化$d[i]$的值为无穷大，初始化$vist[i]$的值为0，表示除源节点外其余节点均未被访问过。
• 首先从未被访问的节点中，找到与源节点权值最小的点$w$，更新其$d[w]$的值，并更新$vist[w]=1$
• 接着更新点$w$连接的边的未被访问的节点$u$，如果$weight[w][u]+d[w]<d[u]$，则更新$d[u]=weight[w][u]+d[w]$，以及$vist[u]=1$，此时已经访问过的节点有$v,w,u$
• 每一次新加入的节点作为更新点，以此寻找未被访问过的点，并更新权值
• 本题求解的是从$1-n$的最短距离，因此当$vist[n]=1$时，程序便可返回权值

图解

• 定义一个数组 $d$，$d[i]$ 表示从源点 0 到顶点 i 的边的权值，比如这里 $d[2] =2 $。初始状态下，$d[1]=0$，如果源点0到某一个点存在边，则将其记录，如果不存在则记录为
• 定义一个集合 $S$ 用于存放距源点最短距离已经确定的顶点。初始状态下，$S = { 1 }$，总所有节点的集合为V

1. 首先，以 1 为源点，到 2 的权值是 2，到 4 的权值是 5，其他情况不存在边
2. 选择最短的一条作为确定找到的最短路径。即到2的权值最小，因此将 2 加入到 $S$ 集合中。此时 $S = { 1，2 }$。
3. 接下来我们看 $V-S$ 中与 2 连接的点3。由于 $d[2]+wight[2-3] < d[3]$，故将 $d[3]$ 更新为 $d[2]+wight[2-3]=5$
4. 在 $V-S$ 的顶点集合中，3，4和源点的权值相同，因此首先将 3 加入到 $S$ 集合中，此时 $S = { 1，2，3 }$。
5. 接下来我们再看 $V-S$ 中与 3连接的点，只有 5 。由于$ d[3] + wight[3-5] < d[5]$，因此将 $d[5] $更新为 $d[3] + wight[3-5]$。
6. 再从 $V-S$ 集合中选择距离源点最近的顶点4，因此将 4 加入到 $S$ 集合中。此时$ S = {1,2,3,4}$
7. 直接将最后一个节点5放入$S$中，运行结束

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int 顶点数
     * @param m int 边数
     * @param graph intvector<vector<>> 一维3个数据，表示顶点到另外一个顶点的边长度是多少
     * @return int
     */
    int findShortestPath(int n, int m, vector<vector<int> >& graph) {
        // write code here
    vector<vector<int>> e(n + 1, vector<int>(n + 1, INT_MAX));
    vector<int> d(n + 1, INT_MAX);
    vector<bool> visit(n + 1, false);
    for (auto& g : graph) 
    {
        e[g[0]][g[1]] = min(g[2], e[g[0]][g[1]]); // 处理重边
    }
    d[1] = 0;
    for (int i = 1; i <= n; i++) 
    {
        int u = -1, minn = INT_MAX;
        for (int j = 1; j <= n; j++) 
        {
            if (!visit[j] && d[j] < minn) //该节点没有被访问过，找到当前情况下距离源点最小的节点，目的是为了将该节点加入到已经访问的集合中
            {
                minn = d[j];//记录权值的最小值，
                u = j;
            }
        }
        if (u == -1)//u没有更新，所有节点均已经访问过，程序结束
        {
            break;
        }
        visit[u] = true;//标记u为已经访问过的节点
        for (int v = 1; v <= n; v++)
        {
            if (!visit[v] && e[u][v] != INT_MAX) //新加入已经访问节点作为中间点，更新其他点(未被访问过,并且两个点之间存在边)距离源点的权值，以便下一次访问最小权值的节点
            {
                if (d[v] > d[u] + e[u][v]) 
                {
                    d[v] = d[u] + e[u][v];//更新源点到v的权值
                }
            }
        }
    }
    return d[n] == INT_MAX ? -1 : d[n];
    }
};

• 时间复杂度：存在内外两层循环，因此时间复杂度为$O(n*m)$
• 空间复杂度: 借助与一个辅助数组和一个标记数组以及一个存储边的数组，空间复杂度为$O(n+n+n*n)=O(n^2)$

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int 顶点数
     * @param m int 边数
     * @param graph intvector<vector<>> 一维3个数据，表示顶点到另外一个顶点的边长度是多少
     * @return int
     */
    int findShortestPath(int n, int m, vector<vector<int> >& graph) {
        // write code here
        vector<int> temp(n,INT_MAX);
        temp[0]=0;//设置源点到自身的值为0
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                if(i+1 == graph[j][0])//第i个点到第i+1个点的值
                {
                    int path = INT_MAX == temp[i] ? INT_MAX : graph[j][2]+temp[i];//节点graph[j][1]距离源点可能的权值
                    temp[graph[j][1] - 1] = min(temp[graph[j][1] - 1], path);//防止有重边的出现
                }
            }
        }
        return temp[n - 1] == INT_MAX ? -1 :temp[n - 1];
    }
    int min(int a,int b)
    {
        return a<=b?a:b;
    }
};

• 时间复杂度：两层循环遍历，外层遍历次数为$n$，内层遍历次数为$m$，因此时间复杂度为$O(n*m)$
• 空间复杂度:  借助于一个辅助数组，用于存放其他点到源点的最小权值，因此复杂度为$O(n)$