本文共 2384 字，大约阅读时间需要 7 分钟。

The Dijkstra's Algorithm for network Graph

Problem:

There are N network nodes, labelled 1 to N.

Given times, a list of travel times as directed edges times[i] = (u, v, w), where u is the source node, v is the target node, and w is the time it takes for a signal to travel from source to target.

Now, we send a signal from a certain node K. How long will it take for all nodes to receive the signal? If it is impossible, return -1.

Input: times = [[2,1,1],[2,3,1],[3,4,1]], N = 4, K = 2Output: 2

Note:

    N will be in the range [1, 100].

    K will be in the range [1, N].     The length of times will be in the range [1, 6000].     All edges times[i] = (u, v, w) will have 1 <= u, v <= N and 0 <= w <= 100.

Implementation by C++ priority_queue

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;class Solution{private: struct cmp { bool operator()(const pair
         
           &l, const pair
          
            &r) { return l.second > r.second; } };public: // implementation by djkstra's algorithm int networkDelayTime(vector
           
            
             > ×, int N, int K) { constexpr int MAX_INT = 999999; vector
             
               Keys(N + 1, MAX_INT); vector
              
                visited(N + 1, false); Keys[K] = 0; // build the adjacents map table. unordered_map
               
                >> adjacents; for (auto &time : times) { int u = time[0], v = time[1], w = time[2]; adjacents[u].push_back(make_pair(v, w)); } priority_queue
                
                 
                  , vector
                  
                   
                    >, cmp> minHeap; minHeap.push(make_pair(K, Keys[K])); while (!minHeap.empty()) { auto u = minHeap.top().first; minHeap.pop(); if(visited[u]) continue; visited[u] = true; for (auto &adjacent : adjacents[u]) { int v = adjacent.first, weight = adjacent.second; if (Keys[u] + weight < Keys[v]) Keys[v] = Keys[u] + weight; minHeap.push(make_pair(v, Keys[v])); } } int maxDelay = 0; for (int i = 1; i <= N; ++i) { if (Keys[i] == MAX_INT) // unreachable return -1; maxDelay = max(maxDelay, Keys[i]); } return maxDelay; }};int main(){ int array[][3] = { {1, 3, 68}, {1, 4, 20}, {4, 1, 65}, {3, 2, 74}, {2, 1, 44}, {3, 4, 61}, {4, 3, 68}, {3, 1, 26}, {5, 1, 60}, {5, 3, 3}, {4, 5, 5}, {2, 5, 36}, {2, 3, 94}, {1, 2, 0}, {3, 5, 90}, {2, 4, 28}, {4, 2, 12}, {5, 4, 52}, {5, 2, 85}, {1, 5, 42}}; vector
                    
                     
                      > times; for(int i = 0; i < sizeof(array) / sizeof(array[0]); ++i) { times.push_back(vector
                      
                       {array[i][0], array[i][1], array[i][2]}); } Solution sol; auto result = sol.networkDelayTime(times, 5, 4); return 0;}
                      
                     
                    
                   
                  
                 
                
               
              
             
            
           
          
         
        
       
      
     
    
   

 

转载地址：http://bwwci.baihongyu.com/