Method dijkstra

java/1514-path-with-maximum-probability.java:37–73

(int start, int end, List<double[]>[] graph)

    }
    
    private double dijkstra(int start, int end, List<double[]>[] graph){
        double[] proTo = new double[graph.length];
        // 初始化为一个去不到的值
        Arrays.fill(proTo, -1);
        proTo[start] = 1;
        
        PriorityQueue<State> pq = new PriorityQueue<State>((a, b) -> {
        return Double.compare(b.proToStart, a.proToStart);
    });
        pq.offer(new State(start, 1));
        
        while (!pq.isEmpty()){
            State cur = pq.poll();
            int curid = cur.id;
            double curproToStart = cur.proToStart;
            
            if (curid == end) {
                return curproToStart;
            }
            
            if (proTo[curid] > curproToStart) {
                continue;
            }
            
            List<double[]> nexts = graph[curid];
            for (double[] next: nexts) {
                double proToNext = proTo[curid] * next[1];
                int idx = (int) next[0];
                if (proToNext > proTo[idx]) {
                    proTo[idx] = proToNext;
                    pq.offer(new State(idx, proToNext));
                }
            }
        }
        
        return 0;
    }
}