We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Path with Maximum Probability

Number: 1325

Difficulty: Medium

Paid? No

Companies: Google, Amazon, BlackRock

Problem Description

Given an undirected weighted graph where each edge has an associated success probability, find the path from a given start node to an end node that maximizes the product of success probabilities along the path. If no such path exists, return 0.

Key Insights

  • The problem can be modeled as a graph traversal where the "distance" is defined in terms of cumulative probability (i.e., product of probabilities).
  • Instead of summing edge weights (like in a standard shortest path problem), multiply probabilities.
  • Dijkstra's algorithm can be adapted to maximize the product by using a max-heap (priority queue) to always extend the path with the highest probability so far.
  • An alternative trick is to transform the multiplication problem into an addition problem by using logarithms, but here a direct multiplication approach with proper priority update is more natural.
  • Maintain an array holding the best probability reached for each node to avoid unnecessary processing.

Space and Time Complexity

Time Complexity: O(E log V), where E is the number of edges and V is the number of vertices. Space Complexity: O(V + E) for the graph representation and auxiliary data structures.

Solution

We use a modified Dijkstra's algorithm:

  1. Build an adjacency list representation of the graph.
  2. Use a max-heap (priority queue) where each element is a pair (current probability, node). The heap always gives the node with the highest probability path computed so far.
  3. Initialize the probability of reaching the start node as 1 and 0 for all other nodes.
  4. While the heap is not empty, pop the node with the highest probability. If it is the end node, return its probability.
  5. For each neighbor, compute the new probability by multiplying the current probability with the probability of the edge connecting to that neighbor. If this new probability is higher than the best known probability for the neighbor, update it and push the neighbor into the heap.
  6. If the end node is never reached, return 0.

Code Solutions

import heapq
from collections import defaultdict

def maxProbability(n, edges, succProb, start, end):
    # Build the graph as an adjacency list
    graph = defaultdict(list)
    for (u, v), prob in zip(edges, succProb):
        graph[u].append((v, prob))
        graph[v].append((u, prob))
    
    # Create a list to store the maximum probability for reaching each node
    max_probs = [0.0] * n
    max_probs[start] = 1.0
    
    # Use a max-heap with negative probabilities (since heapq is a min-heap)
    heap = [(-1.0, start)]
    
    # Process nodes in the order of maximum probability
    while heap:
        # Pop the node with the current highest probability path
        prob, node = heapq.heappop(heap)
        current_prob = -prob
        
        # If we reached the end node, return the probability
        if node == end:
            return current_prob
        
        # If we encounter a probability smaller than the recorded one, skip it
        if current_prob < max_probs[node]:
            continue
        
        # Update the probabilities for neighboring nodes
        for neighbor, edge_prob in graph[node]:
            new_prob = current_prob * edge_prob
            if new_prob > max_probs[neighbor]:
                max_probs[neighbor] = new_prob
                heapq.heappush(heap, (-new_prob, neighbor))
    
    # Return 0 if end is unreachable
    return 0.0

# Example usage:
if __name__ == "__main__":
    n = 3
    edges = [[0,1],[1,2],[0,2]]
    succProb = [0.5,0.5,0.2]
    start, end = 0, 2
    print(maxProbability(n, edges, succProb, start, end))  # Expected output: 0.25
← Back to All Questions