迪杰斯特拉算法（Dijkstra）：求一点到另外一点的最短距离

两种实现方法：

邻接矩阵，时间复杂度O(n^2)

邻接表+优先队列，时间复杂度O(mlogn)（适用于稀疏图）

（n：图的节点数，m：图的边数）

(参考 https://leetcode-cn.com/problems/path-with-maximum-probability/solution/gai-lu-zui-da-de-lu-jing-by-leetcode-solution/)

leetcode经典例题：

（1）

743. 网络延迟时间

https://leetcode-cn.com/problems/network-delay-time/  邻接矩阵，时间复杂度O(n^2)

class Solution {
public:
int networkDelayTime(vector>& times, int N, int K) {
vector visit(N,0);
vector> d(N, vector(N,INT_MAX));
for(auto& t:times)
{
d[t[0]-1][t[1]-1] = t[2];
}
if(N==1)
return 0;

    int result=-1;

    visit\[K-1\] = 1;  
    for(int i=0;i<N-1;i++)  
    {  
        int k, min\_v = INT\_MAX;  
        for(int j=0;j<N;j++)  
        {;  
            if(visit\[j\]==0 && d\[K-1\]\[j\]<min\_v)  
            {  
                min\_v = d\[K-1\]\[j\];  
                k = j;  
            }  
        }  
        if(min\_v == INT\_MAX)  
        {  
            result = -1;  
            break;  
        }

        if(min\_v >result)  
        result = min\_v;

        visit\[k\] = 1;  
        for(int j=0;j<N;j++)  
        {  
            //cout<<"second j:"<<j<<endl;  
            if(visit\[j\]==0 && d\[k\]\[j\]!=INT\_MAX)  
            {  
                if(d\[K-1\]\[j\] > d\[K-1\]\[k\]+d\[k\]\[j\])  
                d\[K-1\]\[j\] = d\[K-1\]\[k\]+d\[k\]\[j\];  
            }  
        }

    }

    return result;  
}  

};

（2）

1514. 概率最大的路径

https://leetcode-cn.com/problems/path-with-maximum-probability/ 邻接表+优先队列，时间复杂度O(mlogn)

class Solution {
public:
double maxProbability(int n, vector>& edges, vector& succProb, int start, int end) {
vector visit(n,0);
vector>> neighbor(n);
for(int i=0;i d(n,0);
d[start] = 1;

    typedef pair<double,int> P;  
    priority\_queue<P, vector<P>, less<P>> q; //最大堆，因为是要求概率值最大，如果是路径最短，应该用最小堆  
    q.push({1,start});  
    while(!q.empty())  
    {  
        auto t = q.top();  
        q.pop();  
        if(visit\[t.second\] == 1)  
        continue;

        visit\[t.second\] = 1;  
        for(auto& i:neighbor\[t.second\])  
        {  
            if(visit\[i.second\]==0 && d\[i.second\]< d\[t.second\]\*i.first)  
            {  
                d\[i.second\] = d\[t.second\]\*i.first;  
                q.push({d\[i.second\], i.second});  
            }  
        }  
    }  
    return d\[end\];  
}  

};