# 1514. Path with Maximum Probability
###### tags: `Leetcode` `Medium` `Dijkstra` `Priority Queue` `BFS`
Link: https://leetcode.com/problems/path-with-maximum-probability/
## 思路 O((V+E)logV) O(V+E)
[Dijkstra算法介绍](https://zhuanlan.zhihu.com/p/40338107)
适用于找起点到终点有最小/最大xx值的路径
每次拿priority queue里面的top，然后把这个top能到达的所有点对应的新value算一下，如果比之前的更好，就加进priority queue里面（这样可能会造成重复），但是不影响结果，但是要注意的是存prev的值并不能让整个code变快，因为priority queue里的全部值不会因为prob table里面值的更新而全部更新，一个idx，在insert进去的时候prob值是多少决定了它在priority queue的位置，that is，两个一样的index不一定在被pop出来的时候是紧挨着的
因为priority queue里面会有duplicate nodes，所以时间复杂度不是O(E+VlogV)

**要注意的是由于priority queue里面存的是integer，但是比较的是double，所以它自带的compare函数的参数应该是integer，而不是double，因此要写成```Queue<Integer> pq = new PriorityQueue<Integer>(Comparator.comparingDouble(i -> -prob[i]));```**

由于一个之前的错误写法困扰了我很久就也放在下面了
之前在priority queue里面装的是node idx 比较的是prob[i]
后来的写法改成priority queue里面装当时拿到的prob和idx
前者priority queue里面会根据已经update了的prob排序
但是后者只会根据当时存下来的prob排序
## Code

class Solution {
    public double maxProbability(int n, int[][] edges, double[] succProb, int start, int end) {
        List<List<int[]>> graph = new ArrayList<>();
        for(int i=0; i<n; i++){
            graph.add(new ArrayList<>());
        }
        for(int i=0; i<edges.length; i++){
            int[] edge = edges[i];
            graph.get(edge[0]).add(new int[]{edge[1], i});
            graph.get(edge[1]).add(new int[]{edge[0], i});
        }
        
        double[] prob = new double[n];
        Queue<double[]> pq = new PriorityQueue<>(Comparator.comparingDouble(a->-a[0]));
        pq.add(new double[]{1.0, start*1.0});
        prob[start] = 1;
        
        while(!pq.isEmpty()){
            double[] curr = pq.poll();
            int idx = (int)curr[1];
            if(idx==end) return curr[0];
            double currProb = curr[0];
            for(int[] next:graph.get(idx)){
                if(currProb*succProb[next[1]]>prob[next[0]]){
                    prob[next[0]]=currProb*succProb[next[1]];
                    pq.add(new double[]{prob[next[0]], next[0]*1.0});
                }
            }
        }
        return 0;
    }
}

之前的错误写法

class Solution {
    public double maxProbability(int n, int[][] edges, double[] succProb, int start, int end) {
        Map<Integer, List<int[]>> map = new HashMap<>();
        for(int i = 0;i < edges.length;i++){
            int u = edges[i][0];
            int v = edges[i][1];
            if(!map.containsKey(u)){
                map.put(u, new ArrayList<>());
            }
            if(!map.containsKey(v)){
                map.put(v, new ArrayList<>());
            }
            map.get(u).add(new int[]{v,i});
            map.get(v).add(new int[]{u,i});
        }
        
        double[] prob = new double[n];
        prob[start] = 1;
        Queue<Integer> pq = new PriorityQueue<Integer>(Comparator.comparingDouble(i -> -prob[i]));
        pq.add(start);
        while(!pq.isEmpty()){
            int curr = pq.poll();
            if(curr == end){
                return prob[end];
            }
            for(int[] next : map.getOrDefault(curr, new ArrayList<>())){
                int neighbor = next[0];
                int idx = next[1];
                if(prob[neighbor] < prob[curr]*succProb[idx]){
                    prob[neighbor] = prob[curr]*succProb[idx];
                    pq.add(neighbor);
                }
            }
        }
        return 0;
    }
}