Leetcode Daily Question 31/08/2024 - 1514. Path with Maximum Probability

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.

from typing import List
import heapq
from collections import defaultdict
class Solution:
  def maxProbability(self, n: int, edges: List[List[int]], succProb: List[int], start_node: int, end_node: int) -> float:
    adj = defaultdict(list)
    for (node, connection), prob in zip(edges, succProb):
      adj[node].append((connection, prob))
      adj[connection].append((node,prob))
      
    
    max_prob = [0] * n
    max_prob[start_node] = 1
    max_heap = [(-1, start_node)]
    
    while max_heap:
      node, prob = heapq.heappop(max_heap)
      prob = -prob 
      
      if node == end_node:
        return prob
      
      for neighbour, n_prob in adj[node]:
        new_prob = prob * n_prob
        if new_prob > max_prob[neighbour]:
          max_prob[neighbour] = new_prob
          heapq.heappush(max_heap, (-new_prob, neighbour))
          
    return 0.0

Explanation:

This is the same question as the one on 27/08/2024, you can find the full explanation there.

The idea of this problem is to modify Dijkstra's Algorithm of shortest path to find the path with max probability.

Instead of using a min_heap, we use a max_heap to keep track of the total probability encountered.

Recall that probabilities of mutually exclusive events multiply.

The time complexity of this is O(n) as we need to traverse every node in the graph.

The space complexity of this is O(n) as we need to store the max prob path.

The full solution can be found near the top of the page.