1514. Path with Maximum Probability

MediumGraphArrayShortest PathHeap (Priority Queue)
Leetcode Link

Problem Description

You are given an undirected graph with n nodes, where these nodes are labeled from 0 to n-1. This graph is defined by its edges, where each edge connects two different nodes (described by an array of two integers [a, b]) and each edge has an associated probability of successful traversal (given in an array succProb). The task is to find the path from a given starting node start to a target node end that has the maximum probability of successfully reaching the target. If no such path exists, the result should be 0. The probabilities are multiplicative along the path, and the result should be within 1e-5 of the actual answer to be considered correct.

Intuition

The problem is a variant of the classic shortest path problem in graph theory. However, instead of finding the shortest distance, we're looking to maximize the probability of success along a path from start to end.

To approach this issue, we can think of the graph as a weighted graph where each weight is the probability of successfully traversing an edge. Then, we can use a max-heap priority queue to keep track of the most promising paths (i.e., paths with the highest probability). This involves adapting Dijkstra's shortest path algorithm to maximize probabilities instead of minimizing distances.

The core idea is to use a max-heap to continuously explore the graph, picking the node-edge combination with the highest probability, and updating the best-known probabilities to other nodes as the algorithm proceeds (the array d). By pushing negative probabilities onto the heap, we effectively turn our max-heap into a min-heap while ensuring we always pop the currently best path in terms of probability.

Once we've exhausted the search or found the target node, we can return the probability associated with the target node, which at this point is the highest probability to reach it from the start node.

Learn more about Graph, Shortest Path and Heap (Priority Queue) patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece๏ผš

A heap is a ...?

Solution Approach

The implementation provided in the solution can be broken down into several key steps using algorithms and data structures:

  1. Graph Representation: The use of a defaultdict to create an adjacency list (g) represents the graph. This allows us to dynamically add vertices (node connections) and associate each with its corresponding success probability.

  2. Initial Setup:

    • A priority queue q is used, specifically implemented as a max-heap here with negative probabilities, to store the nodes along with their current best probability to reach those nodes.
    • An array d is initialized to hold the maximum probabilities of reaching each node from the start, with only the start node's probability initially set to 1 (since the probability of starting at the start node is certain).

  3. Dijkstra's Algorithm Adaptation:

    • We adapt Dijkstra's algorithm in a loop that runs while the priority queue is not empty. We take the node with the current highest probability (most promising path) by using heappop which retrieves and removes the element from the heap with the smallest value, which is actually our largest probability due to the negation trick.
    • We check if the current probability is better than the known probability in the array d for that node (since it's possible that a better path has already been found).

  4. Probability Updates and Queue Management:

    • For each of the node's neighbors (v) and traversal probabilities (t), we calculate the new probability to reach v as the product of t and the max probability to reach the current node (d[u]).
    • If this new probability is an improvement, we update d[v] with it and push the new probability (negated) and the node v onto the priority queue.

  5. Termination and Result:

    • The loop continues until the priority queue is emptied (all paths are explored) or we arrive at the end node.
    • Finally, we return d[end]. This is the maximum probability of reaching the end node from the start node that was recorded throughout the process.

By using these strategies, this algorithm effectively searches paths from the start node to the end node, always pursuing the most promising route in terms of success probability. The usage of negative values in the max-heap is a clever trick to maintain a priority queue structure that can be used with Python's built-in heapq module, which is naturally a min-heap.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What's the relationship between a tree and a graph?

Example Walkthrough

Let's apply the solution approach to a small example graph to illustrate how it works. Assume we have the following graph:

  • The graph has 4 nodes (0, 1, 2, 3).
  • The edges with their associated success probabilities are:
    • (0, 1) with a probability of 0.5
    • (0, 2) with a probability of 0.2
    • (1, 3) with a probability of 0.8
    • (2, 3) with a probability of 0.9
  • The task is to find the maximum probability path from node 0 to node 3.

Step 1: Graph Representation

We represent our graph as an adjacency list: g = { 0: [(1, 0.5), (2, 0.2)], 1: [(0, 0.5), (3, 0.8)], 2: [(0, 0.2), (3, 0.9)], 3: [(1, 0.8), (2, 0.9)] }

Step 2: Initial Setup

  • Initialize the priority queue q and insert the starting node with a probability of 1 (since we're starting at node 0): q = [(-1, 0)].
  • Our maximum probabilities array d will be: [1, 0, 0, 0].

Step 3: Dijkstra's Algorithm Adaptation

  • We pop from the priority queue q. The first node popped is (0, -1). Since -1 (actually 1 in non-negated form) is the highest probability, we start from there.
  • Check and update the probabilities of node 0's neighbors (nodes 1 and 2).

Step 4: Probability Updates and Queue Management

  • Update probabilities:

    • For node 1 via node 0: d[1] = 0.5.
    • For node 2 via node 0: d[2] = 0.2.

  • The priority queue q is updated accordingly: q = [(-0.5, 1), (-0.2, 2)].

  • Continue with the next node in q, which is node 1 with a probability of 0.5.

  • Update node 1's neighbor:

    • For node 3 via node 1: d[3] = max(d[3], d[1] * 0.8) = 0.5 * 0.8 = 0.4.

  • The priority queue is updated: q = [(-0.2, 2), (-0.4, 3)].

  • Continue with the next node in q, which is node 2 with a probability of 0.2.

  • Update node 2's neighbor:

    • For node 3 via node 2: d[3] = max(d[3], d[2] * 0.9) = max(0.4, 0.2 * 0.9) = 0.18.
    • Here, the probability via node 2 (0.18) is not better than the existing path via node 1 (0.4), so we do not update d[3].

Step 5: Termination and Result

  • We arrive at node 3 with the highest probability found of 0.4.
  • Since we have explored all possible paths, the algorithm terminates.

The final probabilities array d is [1, 0.5, 0.2, 0.4]. Therefore, the maximum probability of a successful path from node 0 to node 3 is 0.4.

Solution Implementation

1from typing import List
2from heapq import heappop, heappush
3from collections import defaultdict
4
5class Solution:
6    def maxProbability(
7        self,
8        n: int,
9        edges: List[List[int]],
10        success_probability: List[float],
11        start: int,
12        end: int,
13    ) -> float:
14        # Dictionary to hold the graph representation
15        graph = defaultdict(list)
16      
17        # Building the graph where each edge is associated with its success probability
18        for (node1, node2), success_prob in zip(edges, success_probability):
19            graph[node1].append((node2, success_prob))
20            graph[node2].append((node1, success_prob))
21      
22        # Priority queue to store the nodes along with their probability so far
23        # We use negative probabilities in the priority queue because heapq is a min heap
24        queue = [(-1, start)]
25      
26        # List to hold the maximum success probability to reach each node
27        probabilities = [0] * n
28        probabilities[start] = 1  # Probability to reach start node from itself is 1
29      
30        # Process the queue until it's empty
31        while queue:
32            # Get the node with maximum success probability
33            negative_w, current = heappop(queue)
34            w = -negative_w
35          
36            # If we have already found a better way to the current node, skip it
37            if probabilities[current] > w:
38                continue
39          
40            # Explore neighbors of the current node
41            for neighbor, edge_prob in graph[current]:
42                # Calculate new success probability via this edge
43                new_prob = probabilities[current] * edge_prob
44                # If it's better than the existing probability to the neighbor, update it
45                if probabilities[neighbor] < new_prob:
46                    probabilities[neighbor] = new_prob
47                    # Push the new probability for the neighbor into the queue
48                    heappush(queue, (-new_prob, neighbor))
49      
50        # Return the maximum success probability to reach the end node
51        return probabilities[end]
52
1import java.util.*;
2
3// Utility class to hold a pair of values
4class Pair<T1, T2> {
5    private T1 key;    // First value in the pair
6    private T2 value;  // Second value in the pair
7
8    // Constructor to initialize the pair
9    public Pair(T1 key, T2 value) {
10        this.key = key;
11        this.value = value;
12    }
13
14    // Getter for the key
15    public T1 getKey() {
16        return key;
17    }
18
19    // Getter for the value
20    public T2 getValue() {
21        return value;
22    }
23}
24
25class Solution {
26    public double maxProbability(int nodeCount, int[][] edges, double[] successProbability, int startNode, int endNode) {
27        // Initialize graph as an array of lists to represent an adjacency list
28        List<Pair<Integer, Double>>[] graph = new List[nodeCount];
29        Arrays.setAll(graph, k -> new ArrayList<>());
30
31        // Populate the graph with edges and their corresponding success probabilities
32        for (int i = 0; i < edges.length; ++i) {
33            int from = edges[i][0];
34            int to = edges[i][1];
35            double probability = successProbability[i];
36            graph[from].add(new Pair<>(to, probability));
37            graph[to].add(new Pair<>(from, probability));
38        }
39
40        // Priority queue to help with Dijkstra's algorithm for maximum probability
41        PriorityQueue<Pair<Double, Integer>> queue = new PriorityQueue<>(
42            Comparator.comparingDouble(Pair::getKey).reversed()
43        );
44
45        // Array to keep track of the maximum probability to reach each node
46        double[] probabilities = new double[nodeCount];
47        probabilities[startNode] = 1.0; // Start node has a probability of 1 to reach itself
48        queue.offer(new Pair<>(1.0, startNode));
49
50        // Dijkstra's algorithm to find the maximum probability path
51        while (!queue.isEmpty()) {
52            Pair<Double, Integer> pair = queue.poll();
53            double currentProbability = pair.getKey();
54            int currentNode = pair.getValue();
55
56            // Process each neighbor of the current node
57            for (Pair<Integer, Double> neighbor : graph[currentNode]) {
58                int nextNode = neighbor.getKey();
59                double edgeProbability = neighbor.getValue();
60                double newProbability = currentProbability * edgeProbability;
61
62                // Update the probability for the next node if a higher probability path is found
63                if (probabilities[nextNode] < newProbability) {
64                    probabilities[nextNode] = newProbability;
65                    queue.offer(new Pair<>(newProbability, nextNode));
66                }
67            }
68        }
69
70        // Return the maximum probability to reach the end node
71        return probabilities[endNode];
72    }
73}
74
1#include <vector>
2#include <queue>
3using namespace std;
4
5class Solution {
6public:
7    // Function to find the maximum probability of reaching 'end' node from the 'start' node
8    double maxProbability(int n, vector<vector<int>>& edges, vector<double>& succProb, int start, int end) {
9        vector<vector<pair<int, double>>> graph(n); // Create an adjacency list to represent the graph
10      
11        // Build the graph with the edges and associated success probabilities
12        for (int i = 0; i < edges.size(); ++i) {
13            int a = edges[i][0], b = edges[i][1]; // Extracting the edge nodes
14            double prob = succProb[i]; // Extracting the success probability of the current edge
15          
16            // Adding undirected edge to the graph
17            graph[a].emplace_back(b, prob);
18            graph[b].emplace_back(a, prob);
19        }
20      
21        vector<double> maxProb(n, 0.0); // Probability of reaching each node
22        maxProb[start] = 1.0; // Probability of starting node is 1 as we start from here
23      
24        // Using a queue to perform Breadth First Search (BFS)
25        queue<pair<double, int>> bfsQueue;
26        bfsQueue.push({1.0, start}); // Initialize queue with start node and probability 1
27      
28        // Perform BFS to update maximum probability for each node
29        while (!bfsQueue.empty()) {
30            auto [prob, node] = bfsQueue.front(); // Get the front pair (probability, node)
31            bfsQueue.pop();
32          
33            // For each adjacent node of the current node, update the probability if a higher probability path is found
34            for (auto& edge : graph[node]) {
35                auto [next_node, edge_prob] = edge; // Unpack the edge (adjacent node, edge probability)
36              
37                // If the next node's probability is less than what can be obtained via the current path, update it
38                if (maxProb[next_node] < maxProb[node] * edge_prob) {
39                    maxProb[next_node] = maxProb[node] * edge_prob;
40                    bfsQueue.push({maxProb[next_node], next_node}); // Add to queue to explore further
41                }
42            }
43        }
44      
45        // Return the maximum probability of reaching the 'end' node
46        return maxProb[end];
47    }
48};
49
1// Definition to represent an edge with a node and the probability
2type Edge = [number, number, number];
3
4// Function to find the maximum probability of reaching 'end' starting from 'start'
5function maxProbability(n: number, edges: Edge[], succProb: number[], start: number, end: number): number {
6    // Create an adjacency list to represent the graph
7    const graph: Map<number, Array<[number, number]>> = new Map<number, Array<[number, number]>>();
8
9    // Build the graph with the edges and associated success probabilities
10    edges.forEach((edge, index) => {
11        const [a, b] = edge;
12        const prob: number = succProb[index];
13
14        // Adding undirected edge to the graph
15        if (!graph.has(a)) graph.set(a, []);
16        if (!graph.has(b)) graph.set(b, []);
17        graph.get(a)!.push([b, prob]);
18        graph.get(b)!.push([a, prob]);
19    });
20
21    // Probability of reaching each node
22    const maxProb: number[] = new Array(n).fill(0.0);
23    maxProb[start] = 1.0; // Probability of starting node is 1 as we start from here
24
25    // Using an array to perform Breadth First Search (BFS)
26    const bfsQueue: [number, number][] = [[1.0, start]]; // Initialize queue with start node and probability 1
27
28    // Perform BFS to update maximum probability for each node
29    while(bfsQueue.length > 0) {
30        const [prob, node] = bfsQueue.shift()!; // Get and dequeue the front pair (probability, node)
31
32        // For each adjacent node of the current node, update the probability if a higher probability path is found
33        graph.get(node)?.forEach(([nextNode, edgeProb]) => {
34            // If the next node's probability is less than what can be obtained via the current path, update it
35            if(maxProb[nextNode] < maxProb[node] * edgeProb) {
36                maxProb[nextNode] = maxProb[node] * edgeProb;
37                bfsQueue.push([maxProb[nextNode], nextNode]); // Add to queue to explore further
38            }
39        });
40    }
41
42    // Return the maximum probability of reaching the 'end' node
43    return maxProb[end];
44}
45
46// Usage
47const numberOfNodes: number = 3;
48const edgeList: Edge[] = [[0, 1], [1, 2], [0, 2]];
49const probabilities: number[] = [0.5, 0.5, 0.2];
50const startNode: number = 0;
51const endNode: number = 2;
52
53const result: number = maxProbability(numberOfNodes, edgeList, probabilities, startNode, endNode);
54console.log(result); // Should output the maximum probability
55
Not Sure What to Study? Take the 2-min Quiz๏ผš

What are the two properties the problem needs to have for dynamic programming to be applicable? (Select 2)

Time and Space Complexity

The given code is solving the problem of finding the maximum probability path from the start node to the end node in a graph represented by n nodes and a list of edges with their associated success probabilities.

Time Complexity

The time complexity of the code can be analyzed based on the following points:

  1. Building the graph: The graph is built using a dictionary of adjacency lists. The operation involves iterating over every given edge, which occurs in O(E), where E is the number of edges.

  2. Initializing the heap and distance array: One heap operation (heappush) is done initially, which is O(1), and initializing the distance array of size n is O(n).

  3. While-loop with heap operations: The loop continues until the heap is empty. In the worst case, every vertex is pushed and popped from the heap only once, resulting in at most O(V) heap operations (V is the number of vertices). Each heappop is O(log(V)), and each heappush is O(log(V)). There could be at most E heappush operations since we push to the heap once for every edge in the worst case.

Combining these operations, we get the worst-case time complexity: O(E + V) + O(V) * O(log(V)) + O(E) * O(log(V)) which simplifies to O((V + E) * log(V)).

Space Complexity

The space complexity can be analyzed based on the following factors:

  1. Graph storage: The graph uses an adjacency list representation, requiring O(V + E) space, as each edge shows up twice in the adjacency list.

  2. Priority queue (heap): In the worst case, the heap can contain all vertices, which adds up to O(V) space.

  3. Distance array: An array of size n is used to store the maximum probability for each node from the start node, which is O(V).

Combining these space requirements, we get the total space complexity: O(V + E) + O(V) + O(V) which simplifies to O(V + E).

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

What is the worst case running time for finding an element in a binary tree (not necessarily binary search tree) of size n?

Recommended Readings

Graph Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos graph svg Graph Fundamentals Tree with 0 cycle At this point you should be pretty familiar with trees A tree is a special kind of graph a connected acyclic cycle less graph A graph may contain cycle s and nodes could

Shortest Path

Shortest Path Between A and B Prereq BFS on Graph problems graph_bfs Given an unweighted connected graph return the length of the shortest path between two nodes A and B in terms of the number of edges Assume there always exists a path between nodes A and B Input graph

Heap Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos heap svg Priority Queue and Heap What is the relationship between priority queue and heap Priority Queue is an Abstract Data Type and Heap is the concrete data structure we use to implement a priority queue Priority Queue A priority queue

Got a question?ย Ask the Teaching Assistantย anything you don't understand.

Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.

โ†
โ†‘TA ๐Ÿ‘จโ€๐Ÿซ