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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Path with Maximum Probability

Difficulty: Medium

Problem Description

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.

Key Insights

  • The problem revolves around finding the maximum probability path in a weighted graph, where weights represent probabilities.
  • We can use a graph traversal algorithm that prioritizes paths with higher probabilities, similar to Dijkstra's algorithm.
  • A priority queue can efficiently manage the exploration of nodes based on their success probabilities.
  • The graph is undirected, which means that each edge can be traversed in both directions.

Space and Time Complexity

Time Complexity: O(E log V), where E is the number of edges and V is the number of vertices, due to the use of a priority queue. Space Complexity: O(V + E), for storing the graph and the visited nodes.

Solution

The problem can be solved using a max-heap (priority queue) to always expand the most promising path (highest probability) first. We maintain a probability array to store the maximum probability to reach each node and update it as we explore the graph. If we reach the end node, we return the corresponding probability; if we exhaust all options without reaching the end, we return 0.

Code Solutions

import heapq
from collections import defaultdict

def maxProbability(n, edges, succProb, start, end):
    graph = defaultdict(list)
    
    # Build the graph
    for (a, b), prob in zip(edges, succProb):
        graph[a].append((b, prob))
        graph[b].append((a, prob))

    max_heap = [(-1.0, start)]  # Use negative for max-heap
    probabilities = [0.0] * n
    probabilities[start] = 1.0

    while max_heap:
        prob, node = heapq.heappop(max_heap)
        prob = -prob  # convert back to positive

        if node == end:
            return prob

        for neighbor, edge_prob in graph[node]:
            new_prob = prob * edge_prob
            if new_prob > probabilities[neighbor]:
                probabilities[neighbor] = new_prob
                heapq.heappush(max_heap, (-new_prob, neighbor))

    return 0.0
← Back to All Questions