Dijkstra

743. 网络延迟时间 (opens new window)

class Solution {
    public int networkDelayTime(int[][] times, int n, int k) {
        Map<Integer,List<int[]>> map = new HashMap<>();
        for(int[] t:times){
            map.computeIfAbsent(t[0],e->new ArrayList<>())
            .add(new int[]{t[1],t[2]});
        }
        int[] dist = new int[n+1];// 到自己的距离
        Arrays.fill(dist,Integer.MAX_VALUE);
        dist[k]=0;
        dist[0]=0;
        boolean[] vis = new boolean[n+1];
        PriorityQueue<Integer> pq = new PriorityQueue<>((o1,o2)->{
            return dist[o1]-dist[o2];
        });
        pq.offer(k);
        while(!pq.isEmpty()){
            int cur = pq.poll();
            if(vis[cur]) continue;
            vis[cur] = true;
            List<int[]> neighbors = map.getOrDefault(cur,Collections.emptyList());
            for(int[] neighbor:neighbors){
                int nxt = neighbor[0];
                int d = neighbor[1];
                if(vis[nxt]) continue;
                dist[nxt] = Math.min(dist[nxt],dist[cur]+d);
                pq.offer(nxt);
            }
        }
        int res = Arrays.stream(dist).max().getAsInt();
        return res==Integer.MAX_VALUE?-1:res;
    }
}

1514. 概率最大的路径 (opens new window)

class Solution {
    public double maxProbability(int n, int[][] edges, double[] succProb, int start, int end) {
        Map<Integer,Map<Integer,Double>> map = new HashMap<>();
        for(int i=0;i<edges.length;i++){
            int from = edges[i][0];
            int to = edges[i][1];
            map.computeIfAbsent(from,o->new HashMap<>()).put(to,succProb[i]);
            map.computeIfAbsent(to,o->new HashMap<>()).put(from,succProb[i]);
        }
        double[] dist = new double[n];
        dist[start] = 1;
        PriorityQueue<Integer> pq = new PriorityQueue<>((o1,o2)->{
            return Double.compare(dist[o2],dist[o1]);
        });
        pq.offer(start);
        while(!pq.isEmpty()){
            int cur = pq.poll();
            if(cur==end) continue;
            double p = dist[cur];
            var neighbors = map.getOrDefault(cur,new HashMap<>());
            for(Map.Entry<Integer,Double> neighbor:neighbors.entrySet()){
                int nxt = neighbor.getKey();
                double pNext = p*neighbor.getValue();
                if(pNext>dist[nxt]){
                    dist[nxt] = pNext;
                    pq.offer(nxt);
                }
            }
        }
        return dist[end];
    }
}

Floyd

743. 网络延迟时间 (opens new window)

用于计算每个点到任意一点的最短路；

1. 每轮顶第k行k列与主对角线；
2. 对应行列值象加与(i,j)点取小；

class Solution {
    int INF = 0x3f3f3f3f;
    public int networkDelayTime(int[][] times, int n, int K) {
        int[][] g = new int[n+1][n+1];
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                g[i][j] = i==j?0:INF;
            }
        }
        for(int[] t:times){
            g[t[0]][t[1]] = t[2];
        }
        for(int k=1;k<=n;k++){
            for(int i=1;i<=n;i++){
                for(int j=1;j<=n;j++){
                    g[i][j] = Math.min(g[i][j],g[i][k]+g[k][j]);
                }
            }
        }
        int ret = 0;
        for(int d:g[K]){
            ret = Math.max(ret,d);
        }
        return ret==INF?-1:ret;
    }
}