1514. Path with Maximum Probability
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.
Solution Approach
The implementation provided in the solution can be broken down into several key steps using algorithms and data structures:
-
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. -
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 thestart
node's probability initially set to1
(since the probability of starting at the start node is certain).
- A priority queue
-
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).
- 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
-
Probability Updates and Queue Management:
- For each of the node's neighbors (
v
) and traversal probabilities (t
), we calculate the new probability to reachv
as the product oft
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 nodev
onto the priority queue.
- For each of the node's neighbors (
-
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.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample 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
.
- For node 1 via node 0:
-
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
.
- For node 3 via node 1:
-
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]
.
- For node 3 via node 2:
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
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:
-
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)
, whereE
is the number of edges. -
Initializing the heap and distance array: One heap operation (
heappush
) is done initially, which isO(1)
, and initializing the distance array of sizen
isO(n)
. -
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
). Eachheappop
isO(log(V))
, and eachheappush
isO(log(V))
. There could be at mostE
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:
-
Graph storage: The graph uses an adjacency list representation, requiring
O(V + E)
space, as each edge shows up twice in the adjacency list. -
Priority queue (heap): In the worst case, the heap can contain all vertices, which adds up to
O(V)
space. -
Distance array: An array of size
n
is used to store the maximum probability for each node from the start node, which isO(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.
Given a sorted array of integers and an integer called target, find the element that
equals to the target and return its index. Select the correct code that fills the
___
in the given code snippet.
1def binary_search(arr, target):
2 left, right = 0, len(arr) - 1
3 while left ___ right:
4 mid = (left + right) // 2
5 if arr[mid] == target:
6 return mid
7 if arr[mid] < target:
8 ___ = mid + 1
9 else:
10 ___ = mid - 1
11 return -1
12
1public static int binarySearch(int[] arr, int target) {
2 int left = 0;
3 int right = arr.length - 1;
4
5 while (left ___ right) {
6 int mid = left + (right - left) / 2;
7 if (arr[mid] == target) return mid;
8 if (arr[mid] < target) {
9 ___ = mid + 1;
10 } else {
11 ___ = mid - 1;
12 }
13 }
14 return -1;
15}
16
1function binarySearch(arr, target) {
2 let left = 0;
3 let right = arr.length - 1;
4
5 while (left ___ right) {
6 let mid = left + Math.trunc((right - left) / 2);
7 if (arr[mid] == target) return mid;
8 if (arr[mid] < target) {
9 ___ = mid + 1;
10 } else {
11 ___ = mid - 1;
12 }
13 }
14 return -1;
15}
16
Recommended Readings
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 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
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 Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.