Path With Maximum Probability Leetcode Problem 1514 [Python Solution]

In this blog post, we will explore the LeetCode problem "Path with Maximum Probability," which falls under the category of Advanced Graphs.

We'll provide a Python solution to this problem, explaining both the brute force approach and an efficient approach using Dijkstra's algorithm.

Before we dive into the solutions, let's first understand the problem statement.

Problem Overview

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, the task is to 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.

Example:

Let's consider an example:

Input: n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.2], start = 0, end = 2
Output: 0.25000
Explanation: There are two paths from start to end, one having a probability of success = 0.2, and the other has 0.5 * 0.5 = 0.25.


Understanding the Constraints

Before we dive into the solutions, let's understand the problem's constraints:

• 2 <= n <= 10^4
• 0 <= start, end < n
• start is not equal to end.
• 0 <= a, b < n
• a is not equal to b.
• 0 <= succProb.length == edges.length <= 2*10^4
• 0 <= succProb[i] <= 1
• There is at most one edge between every two nodes.

With these constraints in mind, let's explore the solution.

Brute Force Approach

One way to solve this problem is by using a brute force approach.

The idea is to calculate the probability for each possible path from the start node to the end node, and then return the maximum probability found.

While this approach is valid, it is not the most efficient, as it involves an exponential number of calculations.

We will explore a more efficient approach shortly.

Brute Force Python Code Solution

def maxProbabilityBruteForce(n, edges, succProb, start, end):
    def dfs(node, prob):
        if node == end:
            max_prob[0] = max(max_prob[0], prob)
            return
        visited[node] = True
        for neighbor, edge_prob in graph[node]:
            if not visited[neighbor]:
                dfs(neighbor, prob * edge_prob)
        visited[node] = False

    max_prob = [0.0]  # To keep track of the maximum probability found.

visited = [False] * n
    graph = [[] for _ in range(n)]

    for i in range(len(edges)):
        a, b = edges[i]
        prob = succProb[i]
        graph[a].append((b, prob))
        graph[b].append((a, prob))

    dfs(start, 1.0)  # Start the depth-first search from the start node with probability 1.0. return max_prob[0]


n = 3
edges = [[0,1],[1,2],[0,2]]
succProb = [0.5,0.5,0.2]
start = 0
end = 2
result = maxProbabilityBruteForce(n, edges, succProb, start, end)
print("Maximum Probability (Brute Force):", result)

In this code, we define a dfs function to perform a depth-first search from the start node to the end node, calculating the probability of each path.

We keep track of the maximum probability found in the max_prob list.

This approach works but is not efficient, especially for large graphs.

Efficient Approach with Dijkstra's Algorithm

Dijkstra's algorithm is a well-known algorithm for finding the shortest path in a weighted graph.

In this case, we can modify it to find the maximum probability path.

Instead of minimizing the distance, we aim to maximize the probability.

Let's go through the efficient Python solution using Dijkstra's algorithm.

Efficient Python Code Solution

import collections
import heapq

def maxProbability(n, edges, succProb, start, end):
    # Create an adjacency list to represent the graph.

adj = collections.defaultdict(list)
    for i in range(len(edges)):
        src, dst = edges[i]
        adj[src].append((dst, succProb[i]))
        adj[dst].append((src, succProb[i]))

    # Priority queue for Dijkstra's algorithm.

We use a Max Heap.

pq = [(-1, start)]  # We start with a probability of -1 (inverse of 1).

visited = set()

    while pq:
        prob, cur = heapq.heappop(pq)
        visited.add(cur)

        if cur == end:
            return -prob  # Return the maximum probability (negative due to Max Heap).

for nei, edgeProb in adj[cur]:
            if nei not in visited:
                heapq.heappush(pq, (prob * edgeProb, nei))

    return 0.0  # If no path is found, return 0.0. n = 3
edges = [[0,1],[1,2],[0,2]]
succProb = [0.5,0.5,0.2]
start = 0
end = 2
result = maxProbability(n, edges, succProb, start, end)
print("Maximum Probability (Dijkstra's Algorithm):", result)

In this efficient solution, we use Dijkstra's algorithm to find the maximum probability path.

We start with a priority queue (implemented as a Max Heap) where each element is a pair (prob, cur), representing the current probability and the current node.

We begin with prob as -1 (the inverse of 1) since we want to maximize the probability.

We iterate through the priority queue, popping the node with the highest probability, and mark it as visited.

If we reach the end node, we return the maximum probability (negative value due to Max Heap).

Otherwise, we continue exploring the neighbors, calculating and adding their probabilities to the priority queue.

This efficient approach ensures that we don't need to explore all possible paths, making it suitable for large graphs.

Time and Space Complexity

Let's analyze the time and space complexity of our efficient solution using Dijkstra's algorithm.

Time Complexity:

The time complexity of Dijkstra's algorithm with a priority queue is O(E * log(V)), where E is the number of edges, and V is the number of vertices.

In the worst case, we need

to consider every edge.

Since the number of edges can be at most V^2, the time complexity can be approximated as O(V^2 * log(V)).

Space Complexity:

The space complexity is O(V + E), where V is the number of vertices, and E is the number of edges.

We use additional data structures to store the adjacency list, priority queue, and visited nodes.

Reasoning Behind Our Approach

The reasoning behind our approach is to use Dijkstra's algorithm to find the maximum probability path efficiently.

By keeping track of the maximum probability and using a priority queue, we avoid the need to explore all possible paths, which would result in an exponential time complexity.

Dijkstra's algorithm allows us to greedily select the most promising paths, ultimately leading to the solution with the highest probability.

Related Interview Questions By Company:

• Rotate Array LeetCode
• Number Of Sub Arrays Of Size K And Avg Greater Than Or Equal To Threshold
• Boats To Save People LeetCode

Related Interview Questions By Difficulty:

• Swim In Rising Water LeetCode
• Find Critical And Pseudo Critical Edges In Minimum Spanning Tree
• Alien Dictionary LeetCode

Related Interview Questions By Category:

• Find The Index Of The First Occurrence In A String LeetCode
• Invert Binary Tree LeetCode
• Path With Maximum Probability LeetCode

Conclusion

In this blog post, we tackled the LeetCode problem Path With Maximum Probability by providing both a brute force and an efficient solution using Dijkstra's algorithm.

We explained the problem statement, discussed the constraints, and highlighted the advantages of our efficient approach.

Dijkstra's algorithm provides an elegant and efficient solution for finding the maximum probability path in a weighted graph.

It is a fundamental algorithm for solving various graph-related problems.

If you have any questions, comments, or suggestions, please feel free to share them.

We encourage you to explore the code, test it with different inputs, and further improve your understanding of this problem.

For more coding challenges and tutorials, consider subscribing to our platform and exploring additional resources to enhance your coding skills.

Happy coding!

Question Link

Feel free to comment, ask questions, make suggestions, and share this content with others to help them on their coding journey.