Path to Maximize Probability to Destination - Google Top Interview Questions

                        Solution in C++ :

double solve(vector<vector<int>>& edges, vector<double>& success, int start, int end) {
    unordered_map<int, vector<pair<int, double>>> adj;
    for (int i = 0; i < edges.size(); ++i) {
        int u = edges[i][0], v = edges[i][1];
        double w = success[i];
        adj[u].emplace_back(v, w);
        adj[v].emplace_back(u, w);
    }
    unordered_map<int, double> dist;
    dist[start] = 1;
    priority_queue<pair<double, int>> pq;
    pq.emplace(1, start);
    while (!pq.empty()) {
        auto [cw, u] = pq.top();
        pq.pop();
        if (cw < dist[u]) continue;
        for (auto [v, w] : adj[u]) {
            if (cw * w > dist[v]) {
                dist[v] = cw * w;
                pq.emplace(dist[v], v);
            }
        }
    }
    return dist[end];
}
                    

                        Solution in Java :

import java.util.*;

class Solution {
    class State {
        int node;
        double prob;
        State(int _node, double _prob) {
            node = _node;
            prob = _prob;
        }
    }

    public double solve(int[][] edges, double[] success, int start, int end) {
        Map<Integer, List<State>> map = new HashMap<>();
        Map<Integer, Double> bestProb = new HashMap<>();
        for (int i = 0; i < edges.length; ++i) {
            // Add u, v to graphMap. Add v to u's list of neighbors & vice versa
            int[] edge = edges[i];

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

            map.get(edge[0]).add(new State(edge[1], success[i]));
            map.get(edge[1]).add(new State(edge[0], success[i]));

            // Set best prob. of each node to 0
            bestProb.putIfAbsent(edge[0], 0.0);
            bestProb.putIfAbsent(edge[1], 0.0);
        }

        // Use PriorityQueue that sorts by max probability, add Start node with 100% probability
        Comparator<State> nodeSort = (a, b) -> (((Double) b.prob).compareTo((Double) a.prob));
        PriorityQueue<State> pq = new PriorityQueue<>(nodeSort);
        pq.add(new State(start, 1.0));

        // Begin Dijkstra's
        while (!pq.isEmpty()) {
            // Remove node from PQ
            State state = pq.poll();
            int parent = state.node;
            double prob = state.prob;

            // Reached goal!
            if (parent == end)
                return prob;

            // Explore neighbors
            for (State child : map.getOrDefault(parent, new ArrayList<>())) {
                // Get child's value, prob to visit it, & bestProb
                int childVal = child.node;
                double childProb = child.prob;
                double bestChildProb = bestProb.get(childVal);

                // Add to pq only if it can make a better prob
                if (bestChildProb < prob * childProb) {
                    pq.add(new State(childVal, prob * childProb));
                    bestProb.put(childVal, prob * childProb);
                }
            }
        }

        return 0;
    }
}
                    

                        Solution in Python : 
                            
class Solution:
    def solve(self, edges, success, start, end):
        adj = {}
        distances = {}
        for i, edge in enumerate(edges):
            a, b = edge
            adj[a] = adj.get(a, {})
            adj[b] = adj.get(b, {})
            adj[a][b] = success[i]
            adj[b][a] = success[i]
            distances[a] = 0
            distances[b] = 0

        distances[start] = 1
        heap = [(-1, start)]
        visited = set()

        while heap:
            prob, i = heapq.heappop(heap)
            prob = -prob
            if i in visited:
                continue
            visited.add(i)

            if i == end:
                return prob

            for key, val in adj[i].items():
                if prob * val > distances[key]:
                    distances[key] = prob * val
                    heapq.heappush(heap, (-distances[key], key))

        return 0