实现Dijkstra算法

利用C++实现了Dijkstra算法.

题目来自LeetCode 743.Network Delay Time.

class Solution {
public:
    int networkDelayTime(vector<vector<int>>& times, int N, int K) {
        if(times.empty()) return -1;
        priority_queue<pair<int,int>,vector<pair<int,int>>,compare> pq;
        unordered_map<int,vector<vector<int>>> hash;
        for(auto time:times)
        {
            if(hash.find(time[0])!=hash.end())
            {
                vector<vector<int>> temp=hash[time[0]];
                temp.push_back({time[1],time[2]});
                hash[time[0]]=temp;
            }
            else
                hash[time[0]]={{time[1],time[2]}};
        }
        vector<int> distance(N+1,INT_MAX);
        distance[K]=0;
        pq.push({K,0});
        while(!pq.empty())
        {
            int u=pq.top().first;
            pq.pop();
            if(hash.find(u)!=hash.end())
            {
                vector<vector<int>> Adjs=hash[u];
                for(auto adj:Adjs)
                {
                    int v=adj[0];
                    int w=adj[1];
                    if(distance[v]>distance[u]+w)
                    {
                        distance[v]=distance[u]+w;
                        pq.push({v,distance[v]});
                    }
                }
            }
        }
        int result=0;
        for(int i=1;i<=N;i++)
        {
            if(distance[i]==INT_MAX) return -1;
            result=max(result,distance[i]);
        }
        return result;
    }
    
    struct compare{
        bool operator()(const pair<int,int>& a,const pair<int,int>& b){
            return a.second>b.second;
        }
    };
};

时间复杂度大致为O(vlogv), 其中v为图顶点的数目. 也可以将图用一个二维vector去存储而非用Hash Table, 这样速度能快上10倍左右, 虽然牺牲了一点空间……

struct cmp {
    bool operator()(const pair<int, int>& left, const pair<int, int>& right)  
   {  
       return left.second > right.second;  
   } 
};

class Solution {
public:

    std::vector<int> distances;
    std::vector<vector<pair<int, int>>> edgeList;
    std::priority_queue<pair<int, int>, vector<pair<int,int>>, cmp> paths;
    std::vector<bool> completed;
    
    int networkDelayTime(vector<vector<int>>& times, int N, int K) {
        
        distances = vector<int>(N, -1);
        distances[K-1] = 0;
        completed = vector<bool>(N, false);
        edgeList = vector<vector<pair<int, int>>> (N);
        
        for(auto n: times) { // Make adjacency list
            edgeList[n[0]-1].push_back(make_pair(n[1], n[2]));
        }
        
        paths.push(make_pair(K, 0));
        
        int time = 0, curNode = 0, nextTime = 0;
        
        while(!paths.empty()) {
            
            auto fastestNode = paths.top(); // Get node with lowest time 
            paths.pop();
            
            curNode = fastestNode.first;
            time = fastestNode.second;
            
            if(completed[curNode-1]) continue; // Stop if node is already completed
            
            completed[curNode-1] = true; // Mark node as completed
            
            for(auto n: edgeList[curNode-1]) { // Add edges of this node that has better time as possible paths
                nextTime = time + n.second;
                if(distances[n.first-1] == -1 || nextTime < distances[n.first-1]){
                    distances[n.first-1] = nextTime;
                    paths.push(make_pair(n.first, nextTime));
                }
            }
        }
        
        int best = 0;
        for(auto n: distances) { // Find the max distances, which would be time it takes to reach all nodes
            if(n == -1) {return -1;} // If a node is not reached from starting node
            if(best < n) best = n;
        }
        
        return best;
    }
};

auto gucciGang = []() {std::ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();