leetcode 743网络延迟利用图算法

青旅半醒 2023-05-31 06:48 34阅读 0赞

有 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。

思路：主要抽象成单源最短路径去做  
从第k个节点开始

class Solution {
        
        public int networkDelayTime(int[][] times, int N, int K) {
        
    
            int inf= 1000000000;
                    
            int max = -1;
            int[][] graph= new int[N+1][N+1];
            boolean[] book = new boolean[N+1];
            int[] path = new int[N+1];
            for(int i = 1;i<graph.length;i++)
            {
        
                for(int j = 1;j<graph[i].length;j++)
                {
        
                    graph[i][j] = inf;
                }
            }
    
            for(int[] time:times){
        
                graph[time[0]][time[1]] = time[2];
            }
    
            for(int i = 1;i<path.length;i++)path[i] = 1000000000;
            path[K] = 0;
    
            while(true){
            
                int index = -1;
                int min = Integer.MAX_VALUE;
    
                for(int i = 1;i<graph.length;i++){
        
                    if(path[i]<min && !book[i]){
        
                        min = path[i];
                        index = i;
                    }
                }
    
                if(index ==-1 )break;
                book[index] = true;
    
                for(int i = 1;i<graph[index].length;i++)
                {
        
                       if(graph[index][i]!=inf && path[index]+graph[index][i]<path[i]) 
                            path[i] = path[index]+graph[index][i];
                }
    
    
            }
    
            for(int i = 1;i<path.length;i++)
           {
         if(path[i] == inf)return -1;
            else if(max<path[i])max = path[i];
           }
           return max;
    
        }
    }

Floyd算法

public int networkDelayTime(int[][] times, int N, int K) {
        
    
           int[][] e = new int[N+1][N+1];
           for(int i = 1;i<=N;i++)
           {
        
               for(int j=1;j<=N;j++)
               {
        
                   e[i][j] = 10000000;
               }
           }
           for(int i = 1;i<=N;i++)e[i][i] = 0;   // 必定要有的
           for(int[] time:times){
        
               e[time[0]][time[1]] = time[2];
           }
    
            for(int k = 1;k<=N;k++)
            {
        
                for(int i = 1;i<=N;i++)
                {
        
                    for(int j = 1;j<=N;j++)
                    {
        
                        e[i][j] = Math.min(e[i][j],e[i][k]+e[k][j]);
    
                    }
                }
            }
    
            int res = 0;
            for(int i = 1;i<=N;i++)
            {
        if(e[K][i] ==10000000 )return -1;
            res =Math.max(res,e[K][i]); 
            }
            return res;
        }

C++版本邻接表+堆

class Solution {
        
    public: 
        
        int networkDelayTime(vector<vector<int>>& times, int N, int K) {
        
            
            struct edge{
        
                int to;
                int y;
            };
            typedef pair<int,int> pa;
            vector<edge> b[N];
            
            int inf = 1000000;
            // 结果集
            vector<int> dp(N,inf);
            // 访问控制数组
            bool visit[N];
            for (int i = 0;i < N;i++) {
        
                visit[i] = false;
            }
            for (int i = 0;i < times.size();i++) {
        
                edge g;
                g.to = times[i][1]-1;
                g.y = times[i][2];
                b[times[i][0]-1].push_back(g);
            }
        
            
            // 优先队列,小根堆
            priority_queue<pa,vector<pa>,greater<pa>> p;
            // 起始点
            dp[K-1] = 0;
            p.push({
        0,K-1});
            
            while (!p.empty()) {
        
                pa p1 = p.top();
                p.pop();
                
                int v = p1.second;
                if (visit[v]) continue;
                visit[v] = true;
                
                int size = b[v].size();
                for (int i = 0;i < size;i++) {
        
                   edge newedge =  b[v][i];
                   if (dp[newedge.to] > dp[v] + newedge.y) {
        
                        dp[newedge.to] = dp[v] + newedge.y;
                       p.push({
        dp[newedge.to],newedge.to});
                   } 
                }
            }    
                
            int ret = 0;
             for (int i = 0;i < N;i++) {
        
                 if (dp[i] == inf) return -1;
                ret = max(ret,dp[i]);
             }
            return ret;
        }
    };

Java版本+堆

public static void main(String[] args) {
        
    
            Scanner sc  = new Scanner(new BufferedInputStream(System.in));
    
            int n = sc.nextInt();
            int m = sc.nextInt();
    
            // 存储边集
            List<List<Edge>> graph = new ArrayList<>();
            for (int i = 0;i < n;i++) graph.add(new ArrayList<Edge>());
            for (int i = 0;i < m;i++) {
        
                int x = sc.nextInt() -1;
                int y = sc.nextInt() -1;
                int z = sc.nextInt();
    
                graph.get(x).add(new Edge(x,y,z));
            }
    
            int[] res = dijkstra(graph,0);
    
            System.out.println(INF);
    
        }
    
        private static int[] dijkstra(List<List<Edge>> graph, int i) {
        
            int n = graph.size();
            boolean[] visit = new boolean[n];
            int[] dist = new int[n];
            Queue<Node> queue = new PriorityQueue<>((a,b)->(a.d - b.d));
    
            Arrays.fill(dist,INF);
            dist[i] = 0;
    
            queue.offer(new Node(i,0));
    
            while (!queue.isEmpty()) {
        
                // 索引
                int x = queue.poll().x;
                if (visit[x]) continue;
                List<Edge>edges = graph.get(x);
    
                for (int a = 0;a < edges.size();a++) {
        
                    Edge edge = edges.get(a);
                    int y = edge.y;
                    if (dist[y] > dist[x] + edge.d) {
        
                        dist[y] = dist[x] + edge.d;
                        queue.offer(new Node(y,dist[y]));
                    }
                }
            }
            return dist;
        }