Solution: Path with Maximum Probability

Statement

You are given an undirected weighted graph of n nodes, represented by a 0-indexed list, edges, where edges[i] = [a, b] is an undirected edge connecting the nodes a and b. There is another list succProb, where succProb[i] is the probability of success of traversing the edge edges[i].

Additionally, you are given two nodes, start and end. Your task is to find the path with the maximum probability of success to go from start to end and return its success probability. If there is no path from start to end, return 0.

Constraints:

• $2 \leq$ n $\leq 10^3$

• $0 \leq$ start, end $<$ n

• start $\neq$ end

• $0 \leq$ a, b $<$ n

• a $\neq$ b

• $0 \leq$ succProb.length $==$ edges.length $\leq 2\times10^3$

• $0 \leq$ succProb[i] $\leq 1$

• There is, at most, one edge between every two nodes.

Solution

In this solution, we use a graph-based approach leveraging Dijkstra's algorithm, but instead of minimizing distances, we maximize probabilities. The given graph consists of n nodes connected by edges, each associated with a probability of success. We aim to find the path from the start node to the end node with the highest probability.

First, we construct an adjacency list to represent the graph, where each node maps to a list of neighboring nodes along with the probability of traversing the edge connecting them. Once the graph is built, we use a max heap (priority queue) to process nodes in decreasing order of probability. We initialize the heap with the start node having a probability of $1.0$ because we are already there. As we extract nodes from the heap, we iterate over their neighbors and update their probabilities if a higher probability path is found. This is done by multiplying the current node’s probability with the edge probability leading to the neighbor. If the newly computed probability is greater than the previously recorded probability for that neighbor, we update it and push the neighbor into the heap. The process continues until we either reach the end node (in which case we return the computed probability) or exhaust all possibilities (returning $0.0$ if no path exists).

Let's look at the algorithm steps of this solution:

• Create a dictionary to represent the graph as an adjacency list. For each edge (u, v) in edges, store the probability succProb[i] in both directions as the graph is undirected.

• Create a list max_prob of size n, initialized with $0.0$ (default probability). Set max_prob[start] to $1.0$ because we are 100% certain we are at the start node.

• Create a priority queue, pq (max heap), to always process the most probable path first. Push the start node into the heap with probability $1.0$. Python's default heap is a min heap, so we store the negative probabilities such as $-1.0$ to simulate a max heap.

• Process the nodes in the priority queue, so while the queue is not empty:

  • Pop the node cur_node with the highest probability from the heap. Convert the probability back to a positive value (-cur_prob). If the popped node is the end node, return -cur_prob as the result.

  • For each neighbor of cur_node and the edge probability in the graph, calculate the new probability: new_prob=(−cur_prob) × edge_prob.

    • If new_prob is greater than max_prob[neighbor], update max_prob[neighbor] and push (new_prob, neighbor) into the heap.

  • After exploring all the neighbors of cur_node, clear graph[cur_node] to prevent revisiting already processed nodes.

• If we have exhausted the priority queue without reaching the end, return $0.0$, meaning no path exists.

Let’s look at the following illustration to get a better understanding of the solution: