leetcode_743

• 题目描述
• 题目大意
• 思路描述
• 代码
• 写在最后

题目描述

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

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

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

示例 1：

输入：times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
输出：2

示例 2：

输入：times = [[1,2,1]], n = 2, k = 1
输出：1

示例 3：

输入：times = [[1,2,1]], n = 2, k = 2
输出：-1

提示：

1 <= k <= n <= 100
1 <= times.length <= 6000
times[i].length == 3
1 <= ui, vi <= n
ui != vi
0 <= wi <= 100
所有 (ui, vi) 对都 互不相同（即，不含重复边）

来源：力扣（LeetCode）

题目大意

给一个有向加权图，选择图中任意一个节点为起始点，求最晚所有点都收到信号，若有点没收到信号返回-1

思路描述

此题应该使用迪杰斯特拉的解决办法来获取起始点到其他所有点的最短距离，在寻找到到这些最短距离中的最大距离
所以解题操作应为迪杰斯特+枚举
关于实现迪杰斯特拉的操作如下:

1. 创立一个int数组dist记录起始点到数组下标点的最短距离
2. 将dist数组赋给初始值，除了起始点下标为0其余为正无穷
3. 创立一个boolean数组used记录当前点是否被判定过
4. 创立一个数表示正无穷
5. 遍历dist数组找到未被判定过的最小的距离的下标
6. 通过比较（如何比较请看下图）更新dist数组
7. 重复5，6操作节点次即可确定dist所有值都为最短路径
8. 输出dist数组即为迪杰斯特拉所求的从起始点到所有节点的最短距离

此题完整解法：

1. 将所给数组转化为邻接矩阵
2. 使用迪杰斯特拉找出从起始点到所有点最短距离–枚举
3. 找到所有最短距离中的最大值即为所求

代码

class Solution {
	    public int networkDelayTime(int[][] times, int n, int k) {
	     	// 4. 创立一个数表示正无穷
	    	final int maxNumber=Integer.MAX_VALUE/2;
	    	int[][] matrix=new int[n][n];
	    	for(int i=0;i<n;i++){
	    		Arrays.fill(matrix[i], maxNumber);
	    	}
	    	
	    	for(int i=0;i<times.length;i++){
	    		int x=times[i][0]-1,y=times[i][1]-1;
	    		matrix[x][y]=times[i][2];
	    	}
	    	
	    	// 1. 创立一个int数组dist记录起始点到数组下标点的最短距离
	    	int[] dist=new int[n];
	    	
	    	// 2. 将dist数组赋给初始值，除了起始点下标为0其余为正无穷
	    	Arrays.fill(dist, maxNumber);
	    	dist[k-1]=0;

			// 3. 创立一个boolean数组used记录当前点是否被判定过
			boolean[] used=new boolean[n];
				
			// 7. 重复5，6操作节点次即可确定dist所有值都为最短路径
	    	for(int i=0;i<n;i++){
	    	 	5. 遍历dist数组找到未被判定过的最小的距离的下标
	    		int x=-1;
	    		for(int i1=0;i1<n;i1++){
	    			if(!used[i1]&&(x==-1||dist[i1]<dist[x])){
	    				x=i1;
	    			}
	    		}
	    		used[x]=true;
	    		//6. 通过比较（如何比较请看下图）更新dist数组
	    		for(int i1=0;i1<n;i1++){
	    			dist[i1]=Math.min(dist[i1],dist[x]+matrix[x][i1]);
	    		}

	    		
	    	}
	    	// 8. 输出dist数组即为迪杰斯特拉所求的从起始点到所有节点的最短距离
	    	int max=Arrays.stream(dist).max().getAsInt();
	    	return max==maxNumber?-1:max;
	    	

	    }
	}

写在最后

如果感觉写的还不错的话不妨分享给其他人，以求共同进步！

文章如有错误之处请指出，我会听取并改正！