1514. Path with Maximum Probability (spfa, dijkstra)

BFS (spfa)

https://leetcode.com/problems/path-with-maximum-probability/discuss/731626/Java-Detailed-Explanation-BFS

T: O(e+nm), e is edges len, n is v nums, m is edge nums

S: O(e + n)

class Solution {
    class Pair {
        int node;
        double probability;
        Pair(int node, double probability) {
            this.node = node;
            this.probability = probability;
        }
    }
    public double maxProbability(int n, int[][] edges, double[] succProb, int start, int end) {
        Map<Integer, List<Pair>> map = new HashMap<>();
        for (int i = 0; i < edges.length; i++) { // build graph
            int[] edge = edges[i];
            map.putIfAbsent(edge[0], new ArrayList<>());
            map.putIfAbsent(edge[1], new ArrayList<>());
            
            map.get(edge[0]).add(new Pair(edge[1], succProb[i]));
            map.get(edge[1]).add(new Pair(edge[0], succProb[i]));
        }
        
        double[] probs = new double[n]; // used to record newest probas data
        probs[start] = 1; // init probs[start]
        
        Queue<Integer> queue = new ArrayDeque<>();
        queue.offer(start);
        
        while (!queue.isEmpty()) {
            int cur = queue.poll();
            
            // fecth childs, notice to use getOrDefault
            for (Pair child : map.getOrDefault(cur, new ArrayList<>())) {
                int node = child.node;
                double probability = child.probability;
                
                // if node's probs >= new node's probs, no need to update data and add to queue
                if (probs[node] >= probs[cur]*probability) {
                    continue;
                }
                probs[node] = probs[cur]*probability;
                queue.offer(node);
            }
        }
        
        return probs[end]; // return end node's probs
    }
}

/*
solution1: BFS
因為 BFS 都是用在權重1的狀況下, 這題不是

權重1下, 會標記visited 來避免走過重複的

但因為這題不是權重 1, 所以有可能走重複的路徑會產生更好的結果（這裡是說到 end 的機率要最大

所以這提用 BFS 的話就需要重複走路徑, 直到新路徑並不會比較好時, 才不繼續
if (probs[node] >= probs[cur]*probability) {
    continue;
}

所以在最壞的狀況下, time complexity 可能會指數成長

但這題還是可以通過, 最優解是用 dijkstra

*/

spfa + priority queue

class Solution {
    class Pair {
        int node;
        double probability;
        Pair(int node, double probability) {
            this.node = node;
            this.probability = probability;
        }
    }
    public double maxProbability(int n, int[][] edges, double[] succProb, int start, int end) {
        Map<Integer, List<Pair>> map = new HashMap<>();
        for (int i = 0; i < edges.length; i++) { // build graph
            int[] edge = edges[i];
            map.putIfAbsent(edge[0], new ArrayList<>());
            map.putIfAbsent(edge[1], new ArrayList<>());
            
            map.get(edge[0]).add(new Pair(edge[1], succProb[i]));
            map.get(edge[1]).add(new Pair(edge[0], succProb[i]));
        }
        
        double[] probs = new double[n]; // used to record newest probas data
        probs[start] = 1; // init probs[start]
        
        Queue<Pair> pq = new PriorityQueue<>((a, b) -> (((Double) b.probability).compareTo((Double) a.probability)));
        pq.offer(new Pair(start, 1));
        
        while (!pq.isEmpty()) {
            Pair curNode = pq.poll();
            int cur = curNode.node;
            double prob = curNode.probability;
            
            // fecth childs, notice to use getOrDefault
            for (Pair child : map.getOrDefault(cur, new ArrayList<>())) {
                int node = child.node;
                double probability = child.probability;
                
                // if node's probs >= new node's probs, no need to update data and add to queue
                if (probs[node] >= prob*probability) {
                    continue;
                }
                probs[node] = prob*probability;
                pq.offer(new Pair(node, prob*probability));
            }
        }
        
        return probs[end]; // return end node's probs
    }
}

dijkstra, 保證最後結果是最優

演算法所需的時間為 O((|E|+|V|)\log |V|)}

https://leetcode.com/problems/path-with-maximum-probability/discuss/818701/Java-Dijkstra-template

Time: O((n + E) * logn), n is number of v

space: O(n + E), where E = edges.length.

class Solution {
    class Pair {
        int node;
        double probability;
        Pair(int node, double probability) {
            this.node = node;
            this.probability = probability;
        }
    }
    public double maxProbability(int n, int[][] edges, double[] succProb, int start, int end) {

        // build graph -> double[0]: node, double[1]: parent-to-node prob
        Map<Integer, HashSet<Pair>> map = new HashMap<>();
        for (int i = 0; i < edges.length; ++i) {
            int[] edge = edges[i];

            map.putIfAbsent(edge[0], new HashSet<>());
            map.putIfAbsent(edge[1], new HashSet<>());

            map.get(edge[0]).add(new Pair(edge[1], succProb[i]));
            map.get(edge[1]).add(new Pair(edge[0], succProb[i]));
        }

        Set<Integer> set = new HashSet<>();
        Queue<Pair> pq = new PriorityQueue<>((a, b) -> (((Double) b.probability).compareTo((Double) a.probability)));
        pq.add(new Pair(start, 1.0));

        while (!pq.isEmpty()) {

            Pair state = pq.poll();
            int parent = state.node;
            double prob = state.probability;

            if (parent == end) {
                return prob;
            }
            if (set.contains(parent)) {
                continue;
            }
            set.add(parent);

            for (Pair child : map.getOrDefault(parent, new HashSet<>())) {
                int next = child.node;
                double nextProb = child.probability;

                pq.add(new Pair(next, prob * nextProb));
            }

        }

        return 0;
    }
}

/*
solution1: BFS - O(VE)
因為 BFS 都是用在權重1的狀況下, 這題不是

權重1下, 會標記visited 來避免走過重複的

但因為這題不是權重 1, 所以有可能走重複的路徑會產生更好的結果（這裡是說到 end 的機率要最大

所以這提用 BFS 的話就需要重複走路徑, 直到新路徑並不會比較好時, 才不繼續
if (probs[node] >= probs[cur]*probability) {
    continue;
}

所以在最壞的狀況下, time complexity 可能會指數成長

但這題還是可以通過, 最優解是用 dijkstra

solution2: dijkstra - O(ElogE)

1. build graph
2. pq
3. set exclude duplicate

*/

return use Set

提前終止, 使用 Set 即可,

if (parent == end) {
    return prob;
}
if (visited.contains(parent)) {
    continue;
}
visited.add(parent);

class Solution {
    class Pair {
        int node;
        double probs;
        Pair (int node, double probs) {
            this.node = node;
            this.probs = probs;
        }
    }
    public double maxProbability(int n, int[][] edges, double[] succProb, int start, int end) {
        
        Map<Integer, List<Pair>> graph = buildGraph(edges, succProb);
        Set<Integer> visited = new HashSet<>();
        Queue<Pair> pq = new PriorityQueue<>((a, b) -> (((Double) b.probs).compareTo((Double) a.probs)));
        pq.add(new Pair(start, 1.0));

        while (!pq.isEmpty()) {

            Pair state = pq.poll();
            int parent = state.node;
            double prob = state.probs;

            if (parent == end) {
                return prob;
            }
            if (visited.contains(parent)) {
                continue;
            }
            visited.add(parent);

            for (Pair child : graph.getOrDefault(parent, new ArrayList<>())) {
                int next = child.node;
                double nextProb = child.probs;

                pq.add(new Pair(next, prob * nextProb));
            }

        }
        return 0;
    }
    private Map<Integer, List<Pair>> buildGraph(int[][] edges, double[] succProb) {
        Map<Integer, List<Pair>> map = new HashMap<>();
        for (int i = 0; i < edges.length; i++) {
            int[] edge = edges[i];
            map.computeIfAbsent(edge[0], l -> new ArrayList<>()).add(new Pair(edge[1], succProb[i]));
            map.computeIfAbsent(edge[1], l -> new ArrayList<>()).add(new Pair(edge[0], succProb[i]));
        }
        return map;
     }
}

return use HashMap

如果不提前終止, 一律最後再回傳答案, use hashmap

        return visited.get(end) == null ? 0 : visited.get(end);
// 看是不是訪問過的包含 end, 沒有就是無法到達

class Solution {
    class Pair {
        int node;
        double probs;
        Pair (int node, double probs) {
            this.node = node;
            this.probs = probs;
        }
    }
    public double maxProbability(int n, int[][] edges, double[] succProb, int start, int end) {
        
        Map<Integer, List<Pair>> graph = buildGraph(edges, succProb);
        Map<Integer, Double> visited = new HashMap<>();
        Queue<Pair> pq = new PriorityQueue<>((a, b) -> (((Double) b.probs).compareTo((Double) a.probs)));
        pq.add(new Pair(start, 1.0));

        while (!pq.isEmpty()) {

            Pair state = pq.poll();
            int parent = state.node;
            double prob = state.probs;

            // if (parent == end) {
            //     return prob;
            // }
            if (visited.containsKey(parent)) {
                continue;
            }
            visited.put(parent, prob);

            for (Pair child : graph.getOrDefault(parent, new ArrayList<>())) {
                int next = child.node;
                double nextProb = child.probs;

                pq.add(new Pair(next, prob * nextProb));
            }

        }
        return visited.get(end) == null ? 0 : visited.get(end);
    }
    private Map<Integer, List<Pair>> buildGraph(int[][] edges, double[] succProb) {
        Map<Integer, List<Pair>> map = new HashMap<>();
        for (int i = 0; i < edges.length; i++) {
            int[] edge = edges[i];
            map.computeIfAbsent(edge[0], l -> new ArrayList<>()).add(new Pair(edge[1], succProb[i]));
            map.computeIfAbsent(edge[1], l -> new ArrayList<>()).add(new Pair(edge[0], succProb[i]));
        }
        return map;
     }
}

/*
[[0,1],[1,2],[0,2]]


undirected weighted graph
edge succProb[i].


find maximum probability of success to go from
start to end

if there is no path: 0


use dijkstra: find min distance for weighted graph(single source)

=> trasform to find maximum probability of success to go from start to end (single source)

so use pq, each time we poll the maximum probability node to cal the result
and for dijkstra, use a set to record visited node

     0.5
    0 - 1
 0.2 \  /0.5
      2
      
 the best route: 0 - 1 - 2 = 0.5*0.5
 
 not 0-2 = 0.2
 
 because we use pq, 
 
 so from start 0, probs = 1.0
 then put 1 (0.5), 2(0.2) in to pq,
 
 then pop 1 (probs is 0.5) 
 find 1's childs, then put 2(0.5*0.5 = 0.25) into pq
 
 in pq (2(0.25), 2(0.2)), pop probs higher one
 so all visited => continue
 
 if (visited.size != n) return 0;
 at last return result[end]
 
 time: O((V+E)logV)
 space: O(V+E)

*/

latest version

T: O(ElogE), 把邊加入 PQ (Heap)

S: O(E + n) , map, pq 都用到 E, n -> set 用到(多少個點, 可以說是 v

```java
class Solution {
    class Step {
        int id;
        double prob;
        Step(int id, double prob) {
            this.id = id;
            this.prob = prob;
        }
    }
    public double maxProbability(int n, int[][] edges, double[] succProb, int start, int end) {
        Map<Integer, List<Step>> graph = buildGraph(edges, succProb);
        Set<Integer> visited = new HashSet<>();

        Queue<Step> pq = new PriorityQueue<>((a, b) -> ((Double)b.prob).compareTo((Double)a.prob));
        pq.offer(new Step(start, 1.0)); // start is 1.0

        while (!pq.isEmpty()) {
            Step cur = pq.poll();

            if (visited.contains(cur.id)) {
                continue;
            }
            if (cur.id == end) {
                return cur.prob;
            }
            visited.add(cur.id);

            if (graph.containsKey(cur.id)) {
                for (Step next : graph.get(cur.id)) {
                    pq.offer(new Step(next.id, cur.prob * next.prob));
                }
            }
        }
        return 0; // no any is 0
    }
    private Map<Integer, List<Step>> buildGraph(int[][] edges, double[] succProb) {
        Map<Integer, List<Step>> graph = new HashMap<>();
        for (int i = 0; i < edges.length; i++) {
            graph.putIfAbsent(edges[i][0], new ArrayList<>());
            graph.get(edges[i][0]).add(new Step(edges[i][1], succProb[i]));

            graph.putIfAbsent(edges[i][1], new ArrayList<>());
            graph.get(edges[i][1]).add(new Step(edges[i][0], succProb[i]));
        }
        return graph;
    }
}
```

注意, 還是得要維持一個目前的值 currentProb, 不然盲目的加入到 queue, 會很慢的

還是得比較是不是有更優

```java
class Solution {
    class Step {
        int nodeId;
        double prob;
        Step(int nodeId, double prob) {
            this.nodeId = nodeId;
            this.prob = prob;
        }
    }
    public double maxProbability(int n, int[][] edges, double[] succProb, int start_node, int end_node) {
        Map<Integer, List<Step>> graph = buildGraph(edges, succProb);
        Queue<Step> queue = new PriorityQueue<>((a, b) -> Double.compare(b.prob, a.prob));
        queue.offer(new Step(start_node, 1.0));
        boolean[] visited = new boolean[n];
        double[] currentProb = new double[n];

        while (!queue.isEmpty()) {
            Step cur = queue.poll();
            if (visited[cur.nodeId]) {
                continue;
            }
            visited[cur.nodeId] = true;
            currentProb[cur.nodeId] = cur.prob;

            if (cur.nodeId == end_node) {
                return cur.prob;
            }
            if (graph.containsKey(cur.nodeId)) {
                for (Step next : graph.get(cur.nodeId)) {
                    double newProb = cur.prob * next.prob;
                    if (newProb > currentProb[next.nodeId]) {
                        currentProb[next.nodeId] = newProb;
                        queue.offer(new Step(next.nodeId, newProb));
                    }
                }
            }
        }
        return 0.0;
    }
    private Map<Integer, List<Step>> buildGraph(int[][] edges, double[] succProb) {
        Map<Integer, List<Step>> graph = new HashMap<>();
        for (int i = 0; i < edges.length; i++) {
            int[] edge = edges[i];
            graph.putIfAbsent(edge[0], new ArrayList<>());
            graph.get(edge[0]).add(new Step(edge[1], succProb[i]));
            
            graph.putIfAbsent(edge[1], new ArrayList<>());
            graph.get(edge[1]).add(new Step(edge[0], succProb[i]));
        }
        return graph;
    }
}
```