Path with Maximum Probability

Question Overview:

You are given an undirected weighted graph represented by nodes and edges, where each edge has a success probability of traversal.
The task is to find the path from a specified start node to an end node that maximizes the overall success probability of reaching the end node. If no such path exists, return 0. The answer should be accurate within a tolerance of 1e-5

Leetcode Link: 1514

Solution Overview:

Step-by-Step Approach to Solution

Step 1: Understanding the Problem Constraints

1. Graph Type: The graph is undirected and weighted, where weights represent probabilities of success (values between 0 and 1).
2. Objective: Find the path with the maximum success probability from the start node to the end node.
3. Data Range: The number of nodes and edges could be large, suggesting the need for an efficient algorithm.

Step 2: Initial Algorithm Considerations

Breadth-First Search (BFS) and Depth-First Search (DFS)

• Use Case: These algorithms are typically used for unweighted graphs or for finding simple connectivity between nodes.
• Limitation: In this problem, we need to consider weights (probabilities), so neither BFS nor DFS can directly handle the varying probabilities effectively without modification.

Conclusion: BFS and DFS are not suitable for this problem because they do not account for weights/probabilities.

Step 3: Suitable Algorithms for Weighted Graphs

For weighted graphs, typical algorithms include:

1. Dijkstra's Algorithm:
   • Purpose: Finds the shortest path in a graph with non-negative weights.
   • How It Works: Uses a priority queue (min-heap) to always expand the shortest known distance first.
2. Bellman-Ford Algorithm:
   • Purpose: Finds the shortest path in a graph, capable of handling negative weights.
   • How It Works: Uses dynamic programming to iteratively relax all edges, handling negative weight cycles.

Step 4: Analyzing the Suitability of Dijkstra's Algorithm

• Negative Weights: The problem does not have negative weights (probabilities are between 0 and 1), so Dijkstra’s algorithm can be considered.
• Finding Maximum Probability: Dijkstra’s algorithm traditionally finds the shortest path. However, we want to maximize the path probability.

Step 5: Adapting Dijkstra's Algorithm to Maximize Probability

Dijkstra’s algorithm can be adapted as follows:

• Max-Heap: Instead of a min-heap for the shortest distance, we use a max-heap to prioritize paths with the highest probability.
• Continue Until Completion: Unlike the shortest path, where we can terminate early when reaching the destination optimally, we must process all nodes in our max-heap until it’s empty to ensure finding the maximum probability.

AC Solution

class Solution:
    def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start_node: int, end_node: int) -> float:
        
        start = start_node
        end = end_node

        # create edge node
        graph = defaultdict(list)
        for ind, edge in enumerate(edges):
            src, des, wt = edge[0], edge[1], succProb[ind]
            graph[src].append((wt, des))
            graph[des].append((wt, src))
        
        def perform_dijkstra():
            heap = []
            dis  = [-maxsize]*n
            # probablity to reach start = 1
            dis[start] = 1 

            # (curr_dis, node)
            heappush(heap, (-1, start))

            while heap:
                curr_dis, node = heappop(heap)
                curr_dis = -1*curr_dis

                for wt, child in graph[node]:
                    if dis[child] < curr_dis * wt:
                        dis[child] = curr_dis * wt
                        heappush(heap, (-dis[child], child))


            return 0 if dis[end] == -maxsize else dis[end]
        
        return perform_dijkstra()

Submission Link: here