图中最短路径：网络延迟时间

一、题目描述

有 N 个网络节点，标记为 1 到 N。

给定一个列表 times，表示信号经过有向边的传递时间。 times[i] = (u, v, w)，其中 u 是源节点，v 是目标节点， w 是一个信号从源节点传递到目标节点的时间。

现在，我们从某个节点 K 发出一个信号。需要多久才能使所有节点都收到信号？如果不能使所有节点收到信号，返回 -1。

二、理解题意

• 我们需要找到从给定节点k发出的信号多久后可以到达所有节点。

• 每条边都被赋予了长度（边权），即信号在该边传输所用的时间。

• 观察：从节点k发出的信号到达节点a的最短时间就是在图中节点k到节点a最短路径的长度。

• 题目所求的时间就是距离节点k最远的节点与节点k之间的最短距离。

三、解法一：深度优先遍历

public int[] dist; //dist存储从源节点k到各个节点的最短距离

public int networkDelayTime(int[][] times, int N, int K) {
	//构建有权图的邻接表adj
	ArrayList<ArrayList<int[]>> adj = new ArrayList<ArrayList<int[]>>(N+1);
	for(int i=0; i <= N; i++) 
		adj.add(new ArrayList<int[]>());
	for(int i=0; i < times.length; i++)
		adj.get(times[i][0]).add(new int[]{times[i][1], times[i][2]});
	
	dist = new int[N+1];
	//初始化最短距离为无穷大
	for (int node = 1; node <= N; ++node) 
	dist[node] = Integer.MAX_VALUE;
	
	dfs(adj, K, 0); //从起始节点K开始dfs
	
	int ans = 0; //寻找最短路径中的最大值并返回
	for (int node = 1; node <= N; ++node){
		if (dist[node] == Integer.MAX_VALUE) return -1;
		ans = Math.max(ans, dist[node]);
	}
	
	return ans;
}
public void dfs(ArrayList<ArrayList<int[]>> adj, int node, int elapsed) {
	//剪枝：若之前存在更快到达node节点的路径，本次无需继续扩展该节点
	if (elapsed >= dist[node]) return;
	
	dist[node] = elapsed;
	for(int j=0; j<adj.get(node).size(); j++){
		int[] vert=adj.get(node).get(j);
		dfs(adj, vert[0], elapsed + vert[1]);
	}
}

           

解法二：迪杰斯特拉算法

public int networkDelayTime(int[][] times, int N, int K) {
	//构建有权图的邻接表adj （同基本解法）
	//dist存储从源节点k到各个节点的最短距离，初始化最短距离为无穷大
	int[] dist = new int[N+1];
	for (int node = 1; node <= N; ++node) dist[node] = Integer.MAX_VALUE;
	
	dist[K] = 0;
	boolean[] visited = new boolean[N+1]; //即集合D
	
	while (true) {
		int candNode = -1;
		int candDist = Integer.MAX_VALUE;
		for (int i = 1; i <= N; ++i) { //寻找下一个加入集合D的节点
			if (!visited[i] && dist[i] < candDist) {
				candDist = dist[i];
				candNode = i;
			}
		}
		if (candNode < 0) break; //到所有可达节点的最短路径都寻找完毕，退出循环
		visited[candNode] = true;
		
		for(int j=0; j<adj.get(candNode).size(); j++){
			int[] info =adj.get(candNode).get(j);
			dist[info[0]] = Math.min(dist[info[0]], dist[candNode] + info[1]);
		}
	}
	
	int ans = 0; //寻找最短路径中的最大值并返回
	for (int node = 1; node <= N; ++node){
		if (dist[node] == Integer.MAX_VALUE) return -1;
		ans = Math.max(ans, dist[node]);
	}
	return ans;
}

           

public int networkDelayTime(int[][] times, int n, int k) {

        //构建有权图的邻接表adj （同基本解法）
        List<ArrayList<int []>> adj=new ArrayList<>();
        for(int i=0;i<n+1;i++){
            adj.add(new ArrayList<>());
        }
        for(int [] time:times){
            adj.get(time[0]).add(new int[]{time[1],time[2]});
        }
        //dist存储从源节点k到各个节点的最短距离，初始化最短距离为无穷大
        int[] dist = new int[n+1];
        for (int node = 1; node <= n; ++node) dist[node] = Integer.MAX_VALUE;

        //创建最短距离的前前置节点
        int[] pre= new int[n+1];
        dist[k]=0;

       PriorityQueue<Integer> queue=new PriorityQueue<Integer>((i1,i2)->{
            //如果距离相等
           return dist[i1]-dist[i2];
        });

        //从k开始执行遍历,设置为0，自动浮动到顶点
        queue.offer(k);
       while(!queue.isEmpty()){
           int node= queue.poll();
           //遍历节点，设置相关的distince
           List<int []> ds=adj.get(node);
           for(int [] nextNode:ds){
               if(nextNode[1]+dist[node]<dist[nextNode[0]]){
                   dist[nextNode[0]]=nextNode[1]+dist[node];
                   pre[nextNode[0]]=node;
                   queue.offer(nextNode[0]);
               }
           }
       }


        int ans = 0; //寻找最短路径中的最大值并返回
        for (int node = 1; node <= n; ++node){
            if (dist[node] == Integer.MAX_VALUE) return -1;
            ans = Math.max(ans, dist[node]);
        }
        return ans;
    }