Path with Maximum Probability

class Solution {
public:
    double findMaxProbability(int nodeCount, vector<vector<int>>& connections,
                              vector<double>& probabilities, int startPoint, int endPoint) {
        unordered_map<int, vector<pair<double, int>>> connectivityMap;
        for (int idx = 0; idx < connections.size(); ++idx) {
            int first = connections[idx][0], second = connections[idx][1];
            double prob = probabilities[idx];
            connectivityMap[first].emplace_back(prob, second);
            connectivityMap[second].emplace_back(prob, first);
        }
    
        vector<double> probability(nodeCount, 0.0);
        probability[startPoint] = 1.0;
    
        priority_queue<pair<double, int>> maxHeap;
        maxHeap.emplace(1.0, startPoint);
        while (!maxHeap.empty()) {
            double currentProb = maxHeap.top().first;
            int currentNode = maxHeap.top().second;
            maxHeap.pop();
            if (currentNode == endPoint) {
                return currentProb;
            }
            if (!connectivityMap[currentNode].empty()) {
                for (const auto& next : connectivityMap[currentNode]) {
                    int adjNode = next.second;
                    double edgeProb = next.first;
                    if (currentProb * edgeProb > probability[adjNode]) {
                        probability[adjNode] = currentProb * edgeProb;
                        maxHeap.push({probability[adjNode], adjNode});
                    }
                }
                connectivityMap[currentNode].clear();
            }
        }
    
        return 0.0;
    }
};

The given C++ solution implements a method to determine the path with maximum probability in a graph, where nodes represent points, edges signify possible paths, and probabilities on edges indicate the likelihood of traversing a given path successfully from one node to another. The method findMaxProbability particularly focuses on finding the highest probability from a startPoint to an endPoint within a graph defined by its nodeCount, the set of connections between nodes, and respective probabilities of these connections.

The approach uses a graph representation technique with an unordered_map, where each node maps to a list of pairs containing the probability of travel and the adjacent node. Initial probabilities start with zero, but the start node probability is set to 1 (100%).

For traversing the graph, the solution utilizes a max-heap (priority queue) to always expand the most promising (highest probability) path first. It employs a greedy strategy where, during the graph traversal:

1. If the current node processing is the target endPoint, the highest probability encountered for this path is immediately returned.
2. For each connected node, if traveling there from the current node results in a higher probability than previously encountered, the route is updated with this new higher probability, and the node is added back into the max-heap for potential further exploration.
3. Nodes' connections are cleared from the map once explored to avoid revisiting and recalculating.

If the traversal is completed without reaching the endPoint, indicating no path could be established from startPoint to endPoint, the function returns 0.0, suggesting an impossible journey under given edge probabilities.

This method is particularly efficient for directed and undirected graphs where edge weights (probabilities) influence path selection, leveraging properties of priority-based greedy algorithms for optimal path finding. Its performance depends on graph size (number of nodes and edges) and is directly tied to the complexity of maintaining and processing the priority queue.

class Solution {
    
    public double highestProbability(
        int nodes,
        int[][] connections,
        double[] probabilities,
        int source,
        int target
    ) {
        Map<Integer, List<Pair<Integer, Double>>> adjacencyList = new HashMap<>();
        for (int i = 0; i < connections.length; i++) {
            int src = connections[i][0], dest = connections[i][1];
            double prob = probabilities[i];
            adjacencyList
                .computeIfAbsent(src, x -> new ArrayList<>())
                .add(new Pair<>(dest, prob));
            adjacencyList
                .computeIfAbsent(dest, x -> new ArrayList<>())
                .add(new Pair<>(src, prob));
        }
    
        double[] probability = new double[nodes];
        probability[source] = 1d;
    
        PriorityQueue<Pair<Double, Integer>> queue = new PriorityQueue<>((a, b) ->
            -Double.compare(a.getKey(), b.getKey())
        );
        queue.add(new Pair<>(1.0, source));
        while (!queue.isEmpty()) {
            Pair<Double, Integer> current = queue.poll();
            double currentProb = current.getKey();
            int currentNode = current.getValue();
            if (currentNode == target) {
                return currentProb;
            }
            if (adjacencyList.containsKey(currentNode)) {
                for (Pair<Integer, Double> next : adjacencyList.getOrDefault(
                    currentNode,
                    new ArrayList<>()
                )) {
                    int nextNode = next.getKey();
                    double edgeProb = next.getValue();
                    if (currentProb * edgeProb > probability[nextNode]) {
                        probability[nextNode] = currentProb * edgeProb;
                        queue.add(new Pair<>(probability[nextNode], nextNode));
                    }
                }
                adjacencyList.remove(currentNode);
            }
        }
    
        return 0d;
    }
}

The given Java program is designed to solve the problem of finding the path with the maximum probability between two nodes in a graph. Here's an explanation of the approach and how each part of the code contributes to the solution:

1. Graph Representation: The graph is represented using an adjacency list. For each given connection between nodes, both directions are stored with the corresponding probability. This is because the graph is undirected as indicated by storing both (src, dest) and (dest, src) in the adjacency list.

2. Initialization:

   • A probability array is used to track the highest probability from the source to any other node initialized at 1.0 for the source and 0d for others.
   • A priority queue is utilized to process the nodes based on their highest probabilities in descending order (-Double.compare(a.getKey(), b.getKey())). Initially, it only contains the source node with a probability of 1.0.

3. Core Algorithm:

   • The algorithm uses a greedy approach, repeatedly extracting the node with the highest probability from the priority queue.
   • For each extracted node, it checks all connected nodes. If moving to the adjacent node via the current node results in a higher probability than previously recorded for that node, update the probability and push the node into the queue.
   • This process continues until either the target node is dequeued, in which case its probability is returned as the answer, or the queue is empty, which would result in returning 0d, indicating no path was found.

4. Memory Optimization:

   • Once a node has been processed, it is removed from the adjacency list to avoid reprocessing and further reduce the memory footprint.

This implementation ensures that the algorithm consistently follows the path which, at any point, appears most promising in terms of maximum probability to reach the target node. Key data structures here are the adjacency list for representing the graph, a double array for tracking probabilities to each node, and a priority queue for processing nodes in order of descending probability.

class Solution:
    def maximumProbability(
        self,
        total_nodes: int,
        connection_edges: List[List[int]],
        successProbability: List[float],
        initial_node: int,
        target_node: int,
    ) -> float:
        adjacency_list = defaultdict(list)
        for index, (node1, node2) in enumerate(connection_edges):
            adjacency_list[node1].append((node2, successProbability[index]))
            adjacency_list[node2].append((node1, successProbability[index]))
    
        probability = [0.0] * total_nodes
        probability[initial_node] = 1.0
    
        priority_queue = [(-1.0, initial_node)]
        while priority_queue:
            current_probability, current_node = heapq.heappop(priority_queue)
            if current_node == target_node:
                return -current_probability
    
            # Process node and update probabilities
            if adjacency_list[current_node]:
                for next_node, edge_probability in adjacency_list[current_node]:
                    new_probability = -current_probability * edge_probability
                    if new_probability > probability[next_node]:
                        probability[next_node] = new_probability
                        heapq.heappush(priority_queue, (-probability[next_node], next_node))
                adjacency_list[current_node].clear()  # Clear after visiting
    
        return 0.0

The provided Python script defines a solution for finding the path with the highest probability of success between two nodes in a weighted graph, where edges between nodes have associated success probabilities.

Here is a breakdown of the approach used in the script:

• The graph is represented using an adjacency list, where each node points to a list of its neighbors paired with the edge success probabilities.
• Initialize a list probability with zeros to hold the maximum probability of reaching each node from the initial node, and set the probability of the initial node to 1.0.
• The solution utilizes a priority queue to process nodes in order of their probability efficiently. The negative of the probability is used because Python's heapq implements a min-heap.
• In each iteration of the while loop, pop the node with the current highest probability off the queue. Terminate early if this node is the target node, returning the probability as the negative of the popped value (to revert to positive as originally stored as negative for min-heap priority).
• If not terminating, update the probabilities of neighboring nodes. If a newly calculated probability for a neighbor exceeds its currently stored probability, update the probability and push it onto the priority queue.
• Clear each node's entries in the adjacency list after visiting to prevent re-processing.

The function will return a probability of 0.0 if no path exists between the initial and target nodes. This algorithm essentially implements Djikstra’s algorithm modified to handle probabilities and maximize them, rather than minimizing distances.