题解 | #单源最短路#

class Solution {
public:
    int findShortestPath(int n, int m, vector<vector<int> >& graph) {
        // write code here
        /*单源最短路使用迪杰斯特拉算法。
        初始化时将S集中加入源点，并更新源点的邻接点的距离。
        往后扫描所有尚未加入S集的点，取距离最小者。每加入S集一个顶点，都要相应
        的尝试更新它的邻接点的值。（因为S集中新加入的顶点，只可能影响到它的邻接
        点的长度）*/
        if(graph.size()==0)
            return -1;
        //为每个顶点创建一个标志数组，记录其是否被加入到最短路中。
        vector<bool> flag(n);
        //表明现在每个节点距离节点1的最短距离。
        vector<int> dist(n);
        //对距离,flag数组进行初始化。距离都初始化为正无穷。
        for(int i=0;i<dist.size();i++)
        {
            dist[i]=INT_MAX;
            flag[i]=false;
        }
        //将源点加入进S集中。
        dist[0]=0;
        flag[0]=true;
        //将节点0的邻接点的距离初始化，同时考虑有重边的情况，重边时取最短边。
        for(auto edge:graph){
            if(edge[0]-1==0 && dist[edge[1]-1]>edge[2])
                dist[ edge[1]-1 ]=edge[2];
        }       
        
        while(1)
        {
            int mindistance=INT_MAX;
            int minIndex=-1;
            for(int i=0;i<dist.size();i++)
            {
                //在尚未加入S集的点中，寻找出一个距离最小的点来。
                if(dist[i]<=mindistance && flag[i]==false)
                {
                    minIndex=i;
                    mindistance=dist[i];
                }
            }
            //如果此时扫描出的结果发现剩余的点对S集来说是不可达的，就说明
            //这张图不是连通图，我们已经扫描完了这个连通分量了。
            if(mindistance==INT_MAX)
            {
                //判断目标点是否可达，或者说是否在该连通分量中。如果不在，返回-1
                if(dist[n-1]!=INT_MAX)
                    return dist[n-1];
                return -1;
            }

            //如果所有的点都加入到了S集中，就退出。
            if(minIndex==-1)
            {
                if(dist[n-1]!=INT_MAX)
                    return dist[n-1];
                return -1;
            }
            //遍历图，找出当前dist最小的节点的所有邻接边。
            for(auto edge:graph)
            {
                //由于在edge中记录的点是从1开始的，与数组中从0开始的差了1。所以要减一
                if( (edge[0]-1) == minIndex )
                {
                    //邻接点的下标。记得要减一
                    int adjoinIndex = edge[1]-1;
                    //如果将新点加入S集后，引起了该点的邻接点的最小距离变化，则更新
                    if(dist[adjoinIndex]>dist[minIndex]+edge[2])
                    {
                        dist[adjoinIndex]=dist[minIndex]+edge[2];
                    }
                }
            }
            flag[minIndex]=true;
        }
        return -1;
    }
};