Problem

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

Given two nodes start and end, 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. Your answer will be accepted if it differs from the correct answer by at most 1e-5.

Examples

Example 1:

graph TD
	0([0]) ---|0.5| 1([1])
	1 ---|0.5| 2([2])
	0 ---|0.2| 2

style 0 fill:#f96,stroke:#f66,stroke-width:2px;
style 2 fill:#9f9,stroke:#0f0,stroke-width:2px;
  
Input: n = 3, edges = [ [0,1],[1,2],[0,2] ], succProb = [0.5,0.5,0.2], start = 0, end = 2
Output: 0.25000
Explanation: There are two paths from start to end, one having a probability of success = 0.2 and the other has 0.5 * 0.5 = 0.25.

Example 2:

graph TD
	0([0]) ---|0.5| 1([1])
	1 ---|0.5| 2([2])
	0 ---|0.3| 2

style 0 fill:#f96,stroke:#f66,stroke-width:2px;
style 2 fill:#9f9,stroke:#0f0,stroke-width:2px;	
  
Input: n = 3, edges = [ [0,1],[1,2],[0,2] ], succProb = [0.5,0.5,0.3], start = 0, end = 2
Output: 0.30000

Example 3:

graph TD
	0([0]) ---|0.5| 1([1])
	2([2])

style 0 fill:#f96,stroke:#f66,stroke-width:2px;
style 2 fill:#9f9,stroke:#0f0,stroke-width:2px;
  
Input: n = 3, edges = [ [0,1] ], succProb = [0.5], start = 0, end = 2
Output: 0.00000
Explanation: There is no path between 0 and 2.

Solution

Method 1 - Using Dijkstra Algorithm with PriorityQueue

The approach in Java will be similar to the Python solution, using Dijkstra’s algorithm adapted for finding the max probability path. Here’s how you can implement it:

  1. Graph Representation: Use an adjacency list.
  2. Priority Queue: Use a priority queue to maintain nodes sorted by their maximum probability path.
  3. Relaxation: Update probabilities and push the node to the queue if a higher probability path is found.
  4. Termination Check: Return the probability once the end node is reached; otherwise, return 0 if no path exists.

Video Explanation

Here is the video explanation of the approach below:

Code

Java
public class Solution {
    static class ProbabilityEdge {
        int vertex;
        double probability;

        ProbabilityEdge(int vertex, double probability) {
            this.vertex = vertex;
            this.probability = probability;
        }
    }

    public double maxProbability(int n, int[][] edges, double[] succProb, int start, int end) {
        // Step 1: Create the graph
        Map<Integer, List<ProbabilityEdge>> gr = new HashMap<>();

        for (int i = 0; i < edges.length; i++) {
            int[] edge = edges[i];
            
            int u = edge[0];
            int v = edge[1];
			double prob = succProb[i];
			
            gr.putIfAbsent(u, new ArrayList<>());
            gr.putIfAbsent(v, new ArrayList<>());

            gr.get(u).add(new ProbabilityEdge(v, prob));
            gr.get(v).add(new ProbabilityEdge(u, prob));
        }

        // Step 2: Use a priority queue (max-heap)
        PriorityQueue<ProbabilityEdge> pq = new PriorityQueue<>((a, b) -> Double.compare(b.probability, a.probability));
        
        pq.add(new ProbabilityEdge(start, 1.0));
        
        double[] maxProb = new double[n];
        maxProb[start] = 1.0;

        while (!pq.isEmpty()) {
            // Step 3: Get the ProbabilityEdge with the highest probability
            ProbabilityEdge current = pq.poll();
            int node = current.vertex;
            double prob = current.probability;

            // Step 4: If we reached the end ProbabilityEdge, return the
            // probability
            if (node == end) {
                return prob;
            }

            // Step 5: Relax edges
            for (ProbabilityEdge nei : gr.getOrDefault(node, new ArrayList<>())) {
                int nextNode = nei.vertex;
                double edgeProb = nei.probability;
                double newProb = prob * edgeProb;
                if (newProb > maxProb[nextNode]) {
                    maxProb[nextNode] = newProb;
                    pq.add(new ProbabilityEdge(nextNode, newProb));
                }
            }
        }

        // If we exhaust the queue without finding the end ProbabilityEdge
        return 0.0;
    }
}
Python
import heapq


def maxProbability(n, edges, succProb, start, end):
    # Step 1: Create the graph
    graph = [[] for _ in range(n)]
    for (a, b), prob in zip(edges, succProb):
        graph[a].append((b, prob))
        graph[b].append((a, prob))

    # Step 2: Use a max-heap (in Python, we use a min-heap with negative probabilities)
    max_heap = [(-1.0, start)]  # (-prob, node)
    max_prob = [0.0] * n
    max_prob[start] = 1.0

    while max_heap:
        # Step 3: Get the node with the highest probability
        prob, node = heapq.heappop(max_heap)
        prob = -prob

        # Step 4: If we reached the end node, return the probability
        if node == end:
            return prob

        # Step 5: Relax edges
        for neighbor, edge_prob in graph[node]:
            new_prob = prob * edge_prob
            if new_prob > max_prob[neighbor]:
                max_prob[neighbor] = new_prob
                heapq.heappush(max_heap, (-new_prob, neighbor))

    # If we exhaust the queue without finding the end node
    return 0.0

Complexity

  • ⏰ Time complexity: O(E log V), where E is number of edges, and V is number of nodes or vertices.
    • It takes O(E) time to build graph
    • Inserting 1 element in PQ takes O(log V) time, and each node can be inserted multiple times, which is proportional to E times, hence takes O((E)logV) times
  • 🧺 Space complexity: O(E+V)
    • priority queue will store all nodes, and each node might be added more than once but at most O(V) elements will be in the queue at any time.
    • maxProb array takes O(V) space
    • Graph storage requires O(E+V) space

Method 2 - Using Dijkstra Algorithm closer to BFS

Code

Java
class Solution {
    static class ProbabilityEdge {
        int vertex;
        double prob;

        ProbabilityEdge(int vertex, double prob) {
            this.vertex = vertex;
            this.prob = prob;
        }
    }
    public double maxProbability(int n, int[][] edges, double[] succProb, int start, int end) {
        Map<Integer, List<ProbabilityEdge>> gr = new HashMap<>();
        for (int i = 0; i < edges.length; ++i) {
            int[] edge = edges[i];
            
            int u = edge[0];
            int v = edge[1];
			double prob = succProb[i];
			
            gr.putIfAbsent(u, new ArrayList<>());
            gr.putIfAbsent(v, new ArrayList<>());

            gr.get(u).add(new ProbabilityEdge(v, prob));
            gr.get(v).add(new ProbabilityEdge(u, prob));
        }

        double[] probs = new double[n];  // best prob so far for each node
        Queue<ProbabilityEdge> queue = new LinkedList<>();
        queue.add(new ProbabilityEdge(start, 1.0));

        while (!queue.isEmpty()) {

            ProbabilityEdge curr = queue.poll();
            int parent = curr.vertex;
            double prob = curr.prob;

            for (ProbabilityEdge nei : gr.getOrDefault(parent, new ArrayList<>())) {
                // add to queue only if: it can make a better prob
                double newProb = prob * nei.prob;
                if (probs[nei.vertex] >= newProb) {
                    continue;
                }

                queue.add(new ProbabilityEdge(nei.vertex, newProb));
                probs[nei.vertex] = newProb;
            }

        }

        return probs[end];
    }
}