Leetcode Daily Question 27/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
from collections import defaultdict
import heapq
class solution:
  def maxProbablity(self, n: int, edges: List[List[int]], succProb: List[float]) -> float:
    adjacency_list = defaultdict(list)
    for idx, pair in enumerate(edges):
      node, connection = pair
      adjacency_list[node].append((connection, succProb[idx]))
      adjacency_list[connection].append((node, succProb[idx]))
      
    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 connection, edge_prob in adjacency_list[node]:
        new_prob = edge_prob * prob
        if new_prob > max_prob[connection]:
          max_prob[connection] = new_prob
          heapq.heappush(max_heap, (-new_prob, connection))
    
    return 0

Explanation:

This is similar to finding the shortest path with maximum weight. So we can apply the same ideas to solve this problem.

In particular, we can modify Djikstra's shortest path algorithm to do this.

Djikstra's algorithm finds the shortest path the source node to all other nodes in the (un)directed graph.

It does so by repeatedly selecting the nearest unvisited vertex and calculating the distance to all the unvisited neighboring vertices.

Let's start by defining the undirected graph as an adjacency list and keeping track of the probability associated with each pair of nodes. We use defaultdict from collections to make the process cleaner.

def maxProbability(n, edges, succProb):
  adjacency_list = defaultdict(list)
  for idx, pair in enumerate(edges):
    node, connection = pair
    adjacency_list[node].append((connection, succProb[idx]))
    adjacency_list[connection].append((node, succProb[idx]))

Next, we create list to store the max path probabilities between two nodes.

We initiate the list by defining the max_prob at our start node as 1.

max_prob = [0] * n
max_prob[start_node] = 1

Now for the main algorithm, we would use a max_heap to help us find the path. The max_heap will keep the max probability on top, hence the path.

We explore each unvisited neighbour of our current node to decide what the max probability path is.

max_heap = [(-1,start)]

while max_heap:
  node, prob = heapq.heappop(max_heap)
  prob = -prob # make the probability positive again
  
  if node == end_node:
    return prob
  
  for connection, edge_prob in adjacency_list[node]:
    new_prob = edge_prob * prob
    if new_prob > max_prob[connection]:
      max_prob[connection] = new_prob
      heapq.heappush(max_heap,(connection, -new_prob))
      
return 0 # catches edge cases if graph is empty

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.