Path With Maximum Probability - Leetcode Solution

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.

Solution:

The problem is a graph problem where we need to find the path with the maximum probability of success. We can use the Dijkstra algorithm to solve this problem.

We start by assigning a weight of 1 to the start node and 0 to all other nodes. Then, we create a priority queue and add the start node to it.

We loop through the priority queue until it is empty or we have visited the end node. In each iteration, we extract the node with the highest weight from the priority queue. Then, we loop through all its neighbors and update their weight if their weight is less than the weight of the current node multiplied by the probability of success.

After we have visited the end node or the priority queue is empty, we return the weight of the end node.

Implementation:

We create a graph using a dictionary where each key is a node and the corresponding value is a list of its neighbors and their probabilities of success. Then, we initialize the weights of all nodes to 0 except the start node which is initialized to 1. We create a priority queue and add the start node to it.

We loop through the priority queue while it is not empty or we have not visited the end node. In each iteration, we extract the node with the highest weight from the priority queue. Then, we loop through all its neighbors and update their weight if their weight is less than the weight of the current node multiplied by the probability of success. We also add the updated neighbor to the priority queue.

After we have visited the end node or the priority queue is empty, we return the weight of the end node.

Code:

Here is the Python code for the solution:

import heapq

class Solution:
    def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start: int, end: int) -> float:
        graph = {}
        for i in range(n):
            graph[i] = []
        for i, edge in enumerate(edges):
            a, b = edge
            p = succProb[i]
            graph[a].append((b, p))
            graph[b].append((a, p))
        
        weights = [0] * n
        weights[start] = 1
        pq = []
        heapq.heappush(pq, (-1, start))
        
        while pq:
            weight, node = heapq.heappop(pq)
            if node == end:
                return -weight
            for neighbor, p in graph[node]:
                w = weight * p
                if w < weights[neighbor]:
                    weights[neighbor] = w
                    heapq.heappush(pq, (w, neighbor))
        
        return 0

1