Algorithms for shortest path

public double maxProbability(int n, int[][] edges, double[] succProb, int start, int end) {
    Map<Integer, List<int[]>> graph = new HashMap<>();
    for(int i = 0; i < edges.length; i++) {
        int a = edges[i][0], b = edges[i][1];
        graph.computeIfAbsent(a, key -> new ArrayList<>()).add(new int[]{b,i});
        graph.computeIfAbsent(b, key -> new ArrayList<>()).add(new int[]{a,i});
    }
    double[] prob = new double[n];
    prob[start] = 1d;
    Queue<Integer> queue = new LinkedList<>(Arrays.asList(start));
    while(!queue.isEmpty()) {
        int cur = queue.poll();
        for(int[] a : graph.getOrDefault(cur, Collections.emptyList())) {
            int neighbor = a[0], index = a[1];
            if(prob[cur] * succProb[index] > prob[neighbor]) {
                prob[neighbor] = prob[cur] * succProb[index];
                queue.offer(neighbor);
            }
        }
    }
    return prob[end];
}

public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
    int edges = k+1;
    // dp[i][j] = distance to reach j with at most i edges from src
    int[][] dp = new int[edges+1][n];
    for(int i = 0; i <= edges; i++) {
        Arrays.fill(dp[i], Integer.MAX_VALUE);
        dp[i][src] = 0; // distance to reach src is 0
    }
    for(int i = 1; i <= edges; i++) {
        for(int[] flight : flights) {
            int u = flight[0], v = flight[1], w = flight[2];
            if(dp[i-1][u] != Integer.MAX_VALUE)
                dp[i][v] = Math.min(dp[i][v], dp[i-1][u] + w);
        }
    }
    int distance = dp[edges][dst];
    return distance == Integer.MAX_VALUE ? -1 : distance;
}

public double maxProbability(int n, int[][] edges, double[] succProb, int start, int end) {
    Map<Integer, List<int[]>> graph = new HashMap<>();
    for(int i = 0; i < edges.length; i++) {
        int a = edges[i][0], b = edges[i][1];
        graph.computeIfAbsent(a, key -> new ArrayList<>()).add(new int[]{b,i});
        graph.computeIfAbsent(b, key -> new ArrayList<>()).add(new int[]{a,i});
    }
    double[] prob = new double[n];
    prob[start] = 1d;
    PriorityQueue<Integer> pq = new PriorityQueue<>(Comparator.comparingDouble(i -> -prob[i]));
    pq.offer(start);
    while(!pq.isEmpty()) {
        int cur = pq.poll();
        if(cur == end) return prob[end];
        for(int[] a : graph.getOrDefault(cur, Collections.emptyList())) {
            int neighbor = a[0], index = a[1];
            if(prob[cur] * succProb[index] > prob[neighbor]) {
                prob[neighbor] = prob[cur] * succProb[index];
                pq.offer(neighbor);
            }
        }
    }
    return prob[end];
}

for (int k = 0; k < n; ++k)
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            dis[i][j] = Math.min(dis[i][j], dis[i][k] + dis[k][j]);