✨今日算法一题
文章目录
网络延迟时间
题目描述
思路详解
本题运用Dijkstra 算法。
根据题意，从节点 k 发出的信号，到达节点 x 的时间就是节点 k 到节点 x 的最短路的长度。因此我们需要求出节点 k 到其余所有点的最短路，其中的最大值就是答案。若存在从 k 出发无法到达的点，则返回 −1。
代码与结果
class Solution { public int networkDelayTime(int[][] times, int n, int k) { final int INF = Integer.MAX_VALUE / 2; int[][] g = new int[n][n]; for (int i = 0; i < n; ++i) { Arrays.fill(g[i], INF); } for (int[] t : times) { int x = t[0] - 1, y = t[1] - 1; g[x][y] = t[2]; } int[] dist = new int[n]; Arrays.fill(dist, INF); dist[k - 1] = 0; boolean[] used = new boolean[n]; for (int i = 0; i < n; ++i) { int x = -1; for (int y = 0; y < n; ++y) { if (!used[y] && (x == -1 || dist[y] < dist[x])) { x = y; } } used[x] = true; for (int y = 0; y < n; ++y) { dist[y] = Math.min(dist[y], dist[x] + g[x][y]); } } int ans = Arrays.stream(dist).max().getAsInt(); return ans == INF ? -1 : ans; } }
✨总结
今天主要复习了Dijkstra 算法，这也是很重要的一个算法，也要注意练习哦！
