题目描述

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

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

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

示例

image-20211022095441991

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

数据范围

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

题解

  1. 通过邻接矩阵的方式建图,矩阵初始化为INF
  2. 定义一个数组保存某点到源点的距离
  3. 利用迪杰斯特拉算法求源点到所有点的最短路
    1. 初始化一个visted数组,初始时所有点为false代表该点未确定最短距离
    2. 初始化一个dist数组为INF代表该点到原点的最短距离
    3. dist[k] = 0 源点到源点的距离为0
    4. 循环遍历所有点,先找到未缺定点中距离最小的点记为t
    5. 标记t已确认
    6. 用t更新图中其它点的最短路
  4. 找到最短路距离中最大的即为答案

Coding

Dijkstra&Floyd

class Solution {
int N = 110;
int M = 6010;
//邻接矩阵存图
int[][] w = new int[N][N];
//记录点到原点的最近距离
int[] dist = new int[N];
//记录哪些点被更新
boolean[] visted = new boolean[N];
int INF = 0x3f3f3f3f;
int n,k;
public int networkDelayTime(int[][] times, int _n, int _k) {
this.n = _n;
this.k = _k;

//初始化邻接矩阵
for(int i = 1;i <= n;i++){
for(int j = 1;j <= n;j++){
if(i == j){
w[i][j] = 0;
}else{
w[i][j] = INF;
}
}
}
//存图
for(int[] time:times){
int u = time[0];
int v = time[1];
int c = time[2];
w[u][v] = c;
}
// //最短路
// dijkstra();
// //遍历答案
// int ans = 0;
// for(int i = 1;i <= n;i++){
// ans = Math.max(ans,dist[i]);
// }
floyd();
int ans = 0;
for(int i = 1;i <= n;i++){
ans = Math.max(ans,w[k][i]);
}
return ans > INF / 2 ? -1 : ans;
}
public void dijkstra(){
//初始化visted和dist
Arrays.fill(visted,false);
Arrays.fill(dist,INF);
//起点的最短距离为0
dist[k] = 0;

for(int p = 1;p <= n;p++){
//从未确定的点中找到距离最近的点
int t = -1;
for(int i = 1;i <= n;i++){
if(!visted[i] && (t == -1 || dist[i] < dist[t])){
t = i;
}
}
//标记t已确认
visted[t] = true;
//用t更新其它点
for(int i = 1;i <= n;i++){
dist[i] = Math.min(dist[i],dist[t] + w[t][i]);
}
}
}
public void floyd(){
for(int k = 1;k <= n;k++){
for(int i = 1;i <= n;i++){
for(int j = 1;j <= n;j++){
w[i][j] = Math.min(w[i][j],w[i][k] + w[k][j]);
}
}
}
}

}

Spfa

class Solution {
int N = 110;// 点数
int M = 6010; // 边数
//定义邻接表
int[] he = new int[N];
int[] e = new int[M];
int[] ne = new int[M];
int[] w = new int[M];
int idx = 0;
int INF = 0x3f3f3f3f;
int n,k;
//记录从i点到源点的最短距离为dist[i]
int[] dist = new int[N];
//记录哪个点已在队列中
boolean[] visted = new boolean[N];
//添加一条边
public void add(int a,int b,int c){
e[idx] = b;
ne[idx] = he[a];
he[a] = idx;
w[idx] = c;
idx++;
}
public int networkDelayTime(int[][] ts, int _n, int _k) {
n = _n; k = _k;
// 初始化链表头
Arrays.fill(he, -1);
// 存图
for (int[] t : ts) {
int u = t[0], v = t[1], c = t[2];
add(u, v, c);
}
// 最短路
spfa();
// 遍历答案
int ans = 0;
for (int i = 1; i <= n; i++) {
ans = Math.max(ans, dist[i]);
}
return ans > INF / 2 ? -1 : ans;
}
public void spfa(){
Arrays.fill(visted,false);
Arrays.fill(dist,INF);
dist[k] = 0;
//标记k已经已入队
//使用队列存储编号
Queue<Integer> queue = new LinkedList<>();
queue.offer(k);
visted[k] = true;
while(!queue.isEmpty()){
//每次从队列取出一个节点,并标为未入队
int t = queue.poll();
visted[t] = false;
//用该点更新其它点的最短距离
//如果更新的点,本身未入队,则加入队列中,并标记已入队
for(int i = he[t];i != -1;i = ne[i]){
int j = e[i];
if(dist[j] > dist[t] + w[i]){
dist[j] = dist[t] + w[i];
if(!visted[j]){
queue.offer(j);
visted[j] = true;
}else{
continue;
}
}
}
}
}
}

总结

朴素迪杰斯特拉算法和spfa算法用于单源汇求最短路场景,区别在于迪杰斯特拉只能在无负权边的场景下使用。

Floyd适用于在多源汇场景下求最短路