Path with Maximum Probability

Medium

Asked by:

94 views

Topics:

GraphsGreedy Algorithms

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.

Example 1:

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.

Example 2:

Input: n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.3], start = 0, end = 2
Output: 0.30000

Example 3:

Input: n = 3, edges = [[0,1]], succProb = [0.5], start = 0, end = 2
Output: 0.00000
Explanation: There is no path between 0 and 2.

Constraints:

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

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range for the number of nodes `n`? What is the maximum number of edges?
Are the edge probabilities guaranteed to be between 0 and 1, inclusive?
If there is no path between the start and end nodes, what value should I return? Should I return 0?
Is the graph directed or undirected? If it is undirected, should I treat an edge as traversable in both directions with the same probability?
Can there be multiple edges between the same two nodes? If so, how should I handle the probabilities of these edges?

Brute Force Solution

Approach

The brute force strategy explores every single possible route between the starting point and the destination. For each of these routes, we compute its probability. Finally, we pick the route that has the highest probability.

Here's how the algorithm would work step-by-step:

Start from the starting point.
Consider all the immediate paths you can take from the starting point.
For each of those paths, explore all the paths you can take from the new point.
Continue doing this, branching out to explore every possible sequence of paths you can take.
Whenever you reach the destination, calculate the probability of the path you took to get there.
Remember the highest probability you've seen so far.
If you reach a point where you've already been, or you're going in circles, stop going down that path.
After exploring all possible paths, the highest probability you remembered is the answer.

Code Implementation

def path_with_maximum_probability_brute_force(
    number_of_nodes,
    edges,
    probabilities,
    start_node,
    end_node,
):
    graph = [[] for _ in range(number_of_nodes)]
    for i in range(len(edges)): 
        node_a, node_b = edges[i]
        probability = probabilities[i]
        graph[node_a].append((node_b, probability))
        graph[node_b].append((node_a, probability))

    maximum_probability = 0.0

    def depth_first_search(
        current_node, current_probability, visited_nodes
    ):
        nonlocal maximum_probability

        # If we reach the end node, update the max probability
        if current_node == end_node:
            maximum_probability = max(
                maximum_probability, current_probability
            )
            return

        # Prevent cycles by tracking visited nodes
        visited_nodes.add(current_node)

        for neighbor_node, edge_probability in graph[current_node]:
            if neighbor_node not in visited_nodes:
                new_probability = current_probability * edge_probability
                depth_first_search(
                    neighbor_node,
                    new_probability,
                    set(visited_nodes),
                )

    depth_first_search(start_node, 1.0, set())
    return maximum_probability

Big(O) Analysis

Time Complexity

O((n+m)!) – The described brute force approach explores all possible paths between the start and end nodes in a graph with n nodes and m edges. In the worst case, the algorithm might explore paths that visit all nodes and edges multiple times, potentially leading to factorial growth in the number of paths considered. The number of possible paths can be approximated by (n+m)!, as we might traverse each node and edge in various orders. Therefore the time complexity grows factorially with the combined size of nodes and edges.

Space Complexity

O(N) – The brute force algorithm uses recursion to explore all possible paths. In the worst-case scenario, the recursion depth can reach N, where N is the number of nodes in the graph. Each recursive call adds a new frame to the call stack. Furthermore, the algorithm needs to keep track of visited nodes to avoid cycles. In the worst case, it might need to store all N nodes in a visited set. Thus, the space complexity is dominated by the recursion stack and the visited set, both of which can grow linearly with N.

Optimal Solution

Approach

We're trying to find the path with the highest probability in a network. The best way to do this is to use a method that explores the network gradually, always prioritizing paths that seem most promising so far. This prevents us from wasting time on paths that are unlikely to lead to the best result.

Here's how the algorithm would work step-by-step:

Start at the beginning location, which has a probability of 1 (or 100%).
Keep track of the best probability we've found so far for reaching each location in the network. Initially, all locations (other than the start) have a probability of zero.
Consider each possible move from our current location to a neighboring location.
When moving from one location to another, calculate the new probability of reaching the destination location by multiplying the current probability of the origin location by the probability of the specific path between them.
If the new probability calculated is better than the best probability we've found so far for reaching that destination, update it.
Repeat steps 3-5, always focusing on the location that currently has the highest probability of reaching it. We continue until we have explored all paths that could possibly improve our overall best probability.
Once we've explored the network, the best probability recorded for the final destination is the answer.

Code Implementation

import heapq

def path_with_maximum_probability(number_of_nodes: int, edges: list[list[int]], probabilities: list[float], start_node: int, end_node: int) -> float:

    adjacency_list = [[] for _ in range(number_of_nodes)]
    for i in range(len(edges)): 
        source_node, destination_node = edges[i]
        edge_probability = probabilities[i]
        adjacency_list[source_node].append((destination_node, edge_probability))
        adjacency_list[destination_node].append((source_node, edge_probability))

    max_probability = [0.0] * number_of_nodes
    max_probability[start_node] = 1.0

    # Use a max-heap to prioritize nodes with higher probabilities.
    priority_queue = [(-1.0, start_node)]

    while priority_queue:
        current_probability, current_node = heapq.heappop(priority_queue)
        current_probability = -current_probability

        # If the current probability is less than the max probability, skip.
        if current_probability < max_probability[current_node]:
            continue

        # Iterate through neighbors of the current node.
        for neighbor_node, edge_probability in adjacency_list[current_node]:
            new_probability = current_probability * edge_probability

            # Update probability if a higher one is found.
            if new_probability > max_probability[neighbor_node]:
                max_probability[neighbor_node] = new_probability

                # Negate probability for max-heap.
                heapq.heappush(priority_queue, (-new_probability, neighbor_node))

    # Returns the probability of reaching the end node.
    return max_probability[end_node]

Big(O) Analysis

Time Complexity

O(E + V log V) – The algorithm uses a priority queue (heap) to repeatedly select the node with the highest probability. With V representing the number of vertices (nodes) and E representing the number of edges in the graph, each node is enqueued at most once. Enqueuing a node takes O(log V) time. Since we explore each edge at most once when dequeuing nodes, processing all edges takes O(E) time. Therefore, the overall time complexity is dominated by the cost of heap operations which is O(V log V) in addition to O(E) to go through all the edges. The time complexity is thus O(E + V log V).

Space Complexity

O(N) – The algorithm maintains a probability array to store the best probability found so far for reaching each location. This array has a size equal to the number of locations in the network, denoted as N. Also, a priority queue (or similar data structure) is used to store the locations to explore, prioritizing those with the highest probability, which in the worst case can hold all N locations. Therefore, the auxiliary space used is proportional to the number of locations, N, resulting in O(N) space complexity.

Edge Cases

Case	How to Handle
Empty graph (n=0 or empty edges list)	Return 0.0 as there is no path.
Start and end node are the same	Return 1.0, as the probability of being at the start node is always 1.
No path exists between start and end nodes	Return 0.0 after Dijkstra's algorithm completes without reaching the end node.
Graph contains cycles	Dijkstra's algorithm with a priority queue handles cycles by continuously updating probabilities.
Edge probabilities are zero	Zero probability edges effectively disconnect nodes; Dijkstra's handles this automatically by not traversing them if a better path exists.
Large number of nodes and edges (scalability)	Dijkstra's algorithm with a priority queue provides efficient logarithmic time complexity for node selection, allowing it to scale efficiently.
Floating point precision issues causing incorrect comparisons	Use a small epsilon value for comparing floating point numbers in the priority queue and termination condition.
Negative edge probabilities (invalid input)	Throw an exception or return an error code, as probabilities cannot be negative.

Empty graph (n=0 or empty edges list)

How to Handle:

Return 0.0 as there is no path.

Start and end node are the same

How to Handle:

Return 1.0, as the probability of being at the start node is always 1.

No path exists between start and end nodes

How to Handle:

Return 0.0 after Dijkstra's algorithm completes without reaching the end node.

Graph contains cycles

How to Handle:

Dijkstra's algorithm with a priority queue handles cycles by continuously updating probabilities.

Edge probabilities are zero

How to Handle:

Zero probability edges effectively disconnect nodes; Dijkstra's handles this automatically by not traversing them if a better path exists.

Large number of nodes and edges (scalability)

How to Handle:

Dijkstra's algorithm with a priority queue provides efficient logarithmic time complexity for node selection, allowing it to scale efficiently.

Floating point precision issues causing incorrect comparisons

How to Handle:

Use a small epsilon value for comparing floating point numbers in the priority queue and termination condition.

Negative edge probabilities (invalid input)

How to Handle:

Throw an exception or return an error code, as probabilities cannot be negative.