743.network-delay-time.md

743. 网络延迟时间

• 描述 有 N 个网络节点，标记为 1 到 N。给定一个列表 times，表示信号经过有向边的传递时间。 times[i] = (u, v, w)，其中 u 是源节点，v 是目标节点， w 是一个信号从源节点传递到目标节点的时间。 现在，我们向当前的节点 K 发送了一个信号。需要多久才能使所有节点都收到信号？如果不能使所有节点收到信号，返回 -1。 注意: N 的范围在 [1, 100] 之间。 K 的范围在 [1, N] 之间。 times 的长度在 [1, 6000] 之间。 所有的边 times[i] = (u, v, w) 都有 1 <= u, v <= N 且 0 <= w <= 100

1. 分析：本题属于有权图单源最短路径问题。
2. 实现
   • Dijstra

   class Solution {
   public:
       int networkDelayTime(vector<vector<int>>& times, int N, int K) {
           if(times.empty())   return 0;        
           //把times保存为图（邻接矩阵）
           vector<vector<int>> MatrixGraph(N+1, vector<int>(N+1, INT_MAX));
           for(int i=1; i<N+1; i++)    MatrixGraph[i][i]=0; //对角线元素
           for(auto time : times)
               MatrixGraph[time[0]][time[1]] = time[2];
   
           //Dijstra:求得K到所有节点的最短路径。
           //在这些路径中，找出最大的值，就是本题的解。
           int res=0, i, min_dist, vertex2clollect, v;
           vector<int>collected(N+1, false); //collected表示节点是否被收录
           vector<int>dist(N+1, INT_MAX);  //K到每个节点的[当前]最短距离
           dist[K] = 0;        //起点K到达自己的距离
           
           while(1)
           {
               //未收录节点中，选择dist最小的v收录。
               min_dist=INT_MAX, vertex2clollect=-1;
               for(i=1; i<N+1; i++)
               {
                   if(dist[i] < min_dist && collected[i]==false)
                   {
                       min_dist = dist[i];
                       vertex2clollect = i;
                   }
               }
               if(vertex2clollect == -1)   break;  //这样的v没找到，结束while(1)循环
   
               collected[vertex2clollect] = true;  //收录这个v
               v = vertex2clollect;
               // 遍历v的邻接点i(没有被收录的，条件2。这里犯过错)
               for(i=1; i<N+1; i++)
               {   //INT_MAX再往上加会报错，加一个判断（条件1）
                   if(MatrixGraph[v][i]!=INT_MAX && collected[i]==false  &&  dist[v]+MatrixGraph[v][i] < dist[i])
                   {    //如果邻接点i能够使得K到i的[当前]最短距离dist[i]更小（条件3）
                       dist[i] = dist[v]+MatrixGraph[v][i];
                       //path[i]=v; //记录路径，i的上一个节点是v。本题没有做要求
                   }
               }
           }
           
           // 现在，dist是K到每个节点的[最终]最短距离。
           ////本题要求的是网络延迟时间。所以，找出最大值即可。
           for(i=1; i<N+1; i++)
               res = max(res, dist[i]);
   
           //如果res==INT_MAX，说明图不连通，无解。
           return res==INT_MAX?-1:res;
       }
   };    
   

   • Floyd

   class Solution {
   public:
       int networkDelayTime(vector<vector<int>>& times, int N, int K) {
           if(times.empty())   return 0;    
   
           //Floyd：多源最短路
           //把times保存为图distance（邻接矩阵），保存每一对节点之间的最短距离
           vector<vector<int>> distance(N+1, vector<int>(N+1, INT_MAX));
           for(int i=1; i<N+1; i++)    distance[i][i]=0; //对角线元素
           for(auto time : times)
               distance[time[0]][time[1]] = time[2];        
           
           int kk, i, j;
           for(kk=1; kk<N+1; kk++)
               for(i=1; i<N+1; i++)
                   for(j=1; j<N+1; j++)
                   {
                       if(distance[i][kk]!=INT_MAX && distance[kk][j]!=INT_MAX)
                           distance[i][j] = min(distance[i][j], distance[i][kk]+distance[kk][j]);
                   }
   
           //找最大的distance[K][i]
           int res = 0;
           for(int i=1; i<N+1; i++)
               res = max(res, distance[K][i]);
   
           //如果res==INT_MAX，说明图不连通
           return res==INT_MAX?-1:res;
       }
   };