Path with Maximum Probability solution and explanation
Google
9 more videos on this problem
Path with Maximum Probability - Leetcode 1514 - PythonNeetCodeIO · 13:11 · 19K views
Path with Maximum Probability | Using Dijkstra's | GOOGLE | Leetcode-1514 | Live CodecodestorywithMIK · 22:48 · 13K views
Leetcode 1514. Path with Maximum ProbabilityFraz · 12:38 · 2K views
1514. Path with Maximum Probability (Leetcode Medium)Programming Live with Larry · 10:07 · 1K views
1514. Path with Maximum Probability | Dijktras | LeetCode Daily ChallengeDeep Tech · 12:35 · 1K views
PATH WITH MAXIMUM PROBABILITY | LEETCODE 1514 | PYTHON DIJKSTRA'S SOLUTIONCracking FAANG · 15:38 · 1K views
LeetCode 1514 .- Path with Maximum Probability (Explained Step by Step)An Average Programmer · 24:46 · 833 views
LeetCode1514 Path with Maximum ProbabilityJeevan Kumar - Cracckify · 11:44 · 823 views
Path with Maximum Probability - Leetcode 1514 - PythonTechError · 9:48 · 566 views
Path with Maximum Probability - LeetCode 1514 - PythonAlpha-Code · 16:31 · 217 views
The problem
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^40 <= start, end < nstart != end0 <= a, b < na != b0 <= succProb.length == edges.length <= 2*10^40 <= succProb[i] <= 1- There is at most one edge between every two nodes.
Approach overview
Problem Overview: You are given an undirected graph where each edge has a success probability. Starting from start, reach end with the maximum possible probability by multiplying probabilities along the path. The task is to compute the path whose product of edge probabilities is highest.
Approach 1: Dijkstra's Algorithm with Maximum Product (O(E log V) time, O(V + E) space)
This problem is a variation of the classic shortest path problem. Instead of minimizing distance, you maximize the product of probabilities. Build an adjacency list from the graph, then use a max heap (priority queue) to always expand the node with the highest current probability. Maintain an array where prob[i] stores the best probability found so far for node i. For each popped node, iterate through its neighbors and update their probability if current_prob * edge_prob is larger than the stored value. This greedy expansion works because once a node is processed with the highest probability, no later path can improve it.
Approach 2: Bellman-Ford Algorithm (O(V * E) time, O(V) space)
Bellman-Ford works by repeatedly relaxing all edges. Initialize the start node with probability 1.0 and others with 0. For up to n - 1 iterations, traverse every edge and update both directions: if traveling through one node improves the probability of the other, update it. The multiplication of probabilities replaces the addition used in traditional shortest path problems. This approach is simpler conceptually and does not require a heap, but it scans every edge many times, making it significantly slower for large graphs.
Recommended for interviews: Dijkstra with a max heap is the expected solution. It shows you understand how to adapt classic shortest-path algorithms to maximize products instead of minimizing sums. Bellman-Ford demonstrates the relaxation principle and works as a fallback, but interviewers typically expect the O(E log V) priority queue optimization.
Approach 1: Dijkstra's Algorithm with Maximum Product
The approach involves using Dijkstra's algorithm but instead of finding the shortest path, we need to find the path with the maximum product of probabilities. This can be achieved by using a max-heap (or priority queue) to always extend the path with the largest accumulated probability of success. The algorithm initializes a maximum probability set for each node starting from the start node with a probability of 1, then iteratively updates the probabilities by considering the edges connected to the current node, updating if a path with higher probability is found.
import heapq
class Solution:
def maxProbability(self, n, edges, succProb, start, end):
graph = [[] for _ in range(n)]
for (u, v), prob in zip(edges, succProb):
graph[u].append((v, prob))
graph[v].append((u, prob))
max_prob = [0.0] * n
max_prob[start] = 1.0
heap = [(-1.0, start)]
while heap:
curr_prob, node = heapq.heappop(heap)
curr_prob *= -1
if node == end:
return curr_prob
for neighbor, edge_prob in graph[node]:
if max_prob[neighbor] < curr_prob * edge_prob:
max_prob[neighbor] = curr_prob * edge_prob
heapq.heappush(heap, (-max_prob[neighbor], neighbor))
return 0.0import java.util.*;
public class Solution {
public double maxProbability(int n, int[][] edges, double[] succProb, int start, int end) {
List<List<Pair>> graph = new ArrayList<>();
for (int i = 0; i < n; i++) {
graph.add(new ArrayList<>());
}
for (int i = 0; i < edges.length; i++) {
int u = edges[i][0];
int v = edges[i][1];
double prob = succProb[i];
graph.get(u).add(new Pair(v, prob));
graph.get(v).add(new Pair(u, prob));
}
double[] maxProb = new double[n];
maxProb[start] = 1.0;
PriorityQueue<Pair> pq = new PriorityQueue<>((a, b) -> Double.compare(b.prob, a.prob));
pq.add(new Pair(start, 1.0));
while (!pq.isEmpty()) {
Pair curr = pq.poll();
int node = curr.node;
double prob = curr.prob;
if (node == end) {
return prob;
}
for (Pair neighbor : graph.get(node)) {
int nextNode = neighbor.node;
double edgeProb = neighbor.prob;
if (maxProb[nextNode] < prob * edgeProb) {
maxProb[nextNode] = prob * edgeProb;
pq.add(new Pair(nextNode, maxProb[nextNode]));
}
}
}
return 0.0;
}
private static class Pair {
int node;
double prob;
Pair(int node, double prob) {
this.node = node;
this.prob = prob;
}
}
}#include <vector>
#include <queue>
#include <utility>
using namespace std;
class Solution {
public:
double maxProbability(int n, vector<vector<int>>& edges, vector<double>& succProb, int start, int end) {
vector<vector<pair<int, double>>> graph(n);
for (int i = 0; i < edges.size(); ++i) {
int u = edges[i][0], v = edges[i][1];
double prob = succProb[i];
graph[u].emplace_back(v, prob);
graph[v].emplace_back(u, prob);
}
vector<double> maxProb(n, 0);
maxProb[start] = 1;
priority_queue<pair<double, int>> pq;
pq.emplace(1.0, start);
while (!pq.empty()) {
auto [prob, node] = pq.top();
pq.pop();
if (node == end) return prob;
for (const auto& [nextNode, edgeProb] : graph[node]) {
if (maxProb[nextNode] < prob * edgeProb) {
maxProb[nextNode] = prob * edgeProb;
pq.emplace(maxProb[nextNode], nextNode);
}
}
}
return 0.0;
}
};class Solution {
maxProbability(n, edges, succProb, start, end) {
const graph = new Array(n).fill(0).map(() => []);
for (let i = 0; i < edges.length; i++) {
const [u, v] = edges[i];
const prob = succProb[i];
graph[u].push([v, prob]);
graph[v].push([u, prob]);
}
const maxProb = new Array(n).fill(0);
maxProb[start] = 1;
const pq = new MaxHeap();
pq.insert([1.0, start]);
while (!pq.isEmpty()) {
const [currProb, node] = pq.extractMax();
if (node === end) {
return currProb;
}
for (const [nextNode, edgeProb] of graph[node]) {
if (maxProb[nextNode] < currProb * edgeProb) {
maxProb[nextNode] = currProb * edgeProb;
pq.insert([maxProb[nextNode], nextNode]);
}
}
}
return 0;
}
}
class MaxHeap {
constructor() {
this.heap = [];
}
insert(pair) {
this.heap.push(pair);
this._heapifyUp();
}
extractMax() {
[this.heap[0], this.heap[this.heap.length - 1]] = [this.heap[this.heap.length - 1], this.heap[0]];
const max = this.heap.pop();
this._heapifyDown();
return max;
}
isEmpty() {
return this.heap.length === 0;
}
_heapifyUp() {
let index = this.heap.length - 1;
while (index > 0) {
let element = this.heap[index];
let parentIndex = Math.floor((index - 1) / 2);
let parent = this.heap[parentIndex];
if (parent[0] >= element[0]) break;
this.heap[index] = parent;
this.heap[parentIndex] = element;
index = parentIndex;
}
}
_heapifyDown() {
let index = 0;
const length = this.heap.length;
const element = this.heap[0];
while (true) {
let leftChildIndex = 2 * index + 1;
let rightChildIndex = 2 * index + 2;
let leftChild, rightChild;
let swap = null;
if (leftChildIndex < length) {
leftChild = this.heap[leftChildIndex];
if (leftChild[0] > element[0]) {
swap = leftChildIndex;
}
}
if (rightChildIndex < length) {
rightChild = this.heap[rightChildIndex];
if (
(swap === null && rightChild[0] > element[0]) ||
(swap !== null && rightChild[0] > leftChild[0])
) {
swap = rightChildIndex;
}
}
if (swap === null) break;
this.heap[index] = this.heap[swap];
this.heap[swap] = element;
index = swap;
}
}
}using System;
using System.Collections.Generic;
public class Solution {
public double MaxProbability(int n, int[][] edges, double[] succProb, int start, int end) {
List<List<Tuple<int, double>>> graph = new List<List<Tuple<int, double>>>();
for (int i = 0; i < n; i++) {
graph.Add(new List<Tuple<int, double>>());
}
for (int i = 0; i < edges.Length; i++) {
int u = edges[i][0], v = edges[i][1];
double prob = succProb[i];
graph[u].Add(Tuple.Create(v, prob));
graph[v].Add(Tuple.Create(u, prob));
}
double[] maxProb = new double[n];
maxProb[start] = 1.0;
PriorityQueue<Tuple<double, int>, double> pq = new();
pq.Enqueue(Tuple.Create(1.0, start), -1.0);
while (pq.Count > 0) {
var (currProb, node) = pq.Dequeue();
currProb *= -1;
if (node == end) return currProb;
foreach (var (nextNode, edgeProb) in graph[node]) {
if (maxProb[nextNode] < currProb * edgeProb) {
maxProb[nextNode] = currProb * edgeProb;
pq.Enqueue(Tuple.Create(maxProb[nextNode], nextNode), -maxProb[nextNode]);
}
}
}
return 0.0;
}
}The implementation uses a max-heap to prioritize nodes with a larger accumulated probability. The graph is represented using adjacency lists. Initially, the start node has an accumulated probability of 1.0, and we update the probabilities for its connected nodes through the priority queue. By always processing the node with the largest probability, and updating its neighbors accordingly, we ensure the most probable path is found. If the end node is reached, the current probability is returned; otherwise, 0.0 is returned indicating no path exists.
Time Complexity: O(E log V), where E is the number of edges and V is the number of vertices, due to the use of the priority queue.
Space Complexity: O(V + E), for storing the graph and additional data structures like the probability set and heap.
Approach 2: Bellman-Ford Algorithm
The Bellman-Ford algorithm traditionally calculates shortest paths in a weighted graph and can be adapted here to maximize a product instead. Given the properties of logarithms, maximizing the product of probabilities can be converted to minimizing the sum of the negative logarithm values, allowing direct use of Bellman-Ford's relaxation principle. This transformation reduces the problem of maximizing path probabilities to a more conventional structure that minimization algorithms handle well, iterating across all edges and vertices.
import math
class Solution:
def maxProbability(self, n, edges, succProb, start, end):
logProb = [-math.inf] * n
logProb[start] = 0
for _ in range(n - 1):
updated = False
for (u, v), prob in zip(edges, succProb):
lg = math.log(prob)
if logProb[u] != -math.inf and logProb[u] + lg > logProb[v]:
logProb[v] = logProb[u] + lg
updated = True
if logProb[v] != -math.inf and logProb[v] + lg > logProb[u]:
logProb[u] = logProb[v] + lg
updated = True
if not updated:
break
return math.exp(logProb[end]) if logProb[end] != -math.inf else 0.0import java.util.Arrays;
public class Solution {
public double maxProbability(int n, int[][] edges, double[] succProb, int start, int end) {
double[] logProb = new double[n];
Arrays.fill(logProb, Double.NEGATIVE_INFINITY);
logProb[start] = 0;
for (int i = 0; i < n - 1; i++) {
boolean updated = false;
for (int j = 0; j < edges.length; j++) {
int u = edges[j][0], v = edges[j][1];
double logValue = Math.log(succProb[j]);
if (logProb[u] != Double.NEGATIVE_INFINITY && logProb[u] + logValue > logProb[v]) {
logProb[v] = logProb[u] + logValue;
updated = true;
}
if (logProb[v] != Double.NEGATIVE_INFINITY && logProb[v] + logValue > logProb[u]) {
logProb[u] = logProb[v] + logValue;
updated = true;
}
}
if (!updated) break;
}
return logProb[end] != Double.NEGATIVE_INFINITY ? Math.exp(logProb[end]) : 0.0;
}
}#include <vector>
#include <cmath>
#include <limits>
using namespace std;
class Solution {
public:
double maxProbability(int n, vector<vector<int>>& edges, vector<double>& succProb, int start, int end) {
vector<double> logProb(n, -numeric_limits<double>::infinity());
logProb[start] = 0;
for (int i = 0; i < n - 1; ++i) {
bool updated = false;
for (int j = 0; j < edges.size(); ++j) {
int u = edges[j][0], v = edges[j][1];
double logProbVal = log(succProb[j]);
if (logProb[u] != -numeric_limits<double>::infinity() && logProb[u] + logProbVal > logProb[v]) {
logProb[v] = logProb[u] + logProbVal;
updated = true;
}
if (logProb[v] != -numeric_limits<double>::infinity() && logProb[v] + logProbVal > logProb[u]) {
logProb[u] = logProb[v] + logProbVal;
updated = true;
}
}
if (!updated) break;
}
return logProb[end] != -numeric_limits<double>::infinity() ? exp(logProb[end]) : 0.0;
}
};class Solution {
maxProbability(n, edges, succProb, start, end) {
const logProb = new Array(n).fill(-Infinity);
logProb[start] = 0;
for (let i = 0; i < n - 1; i++) {
let updated = false;
for (let j = 0; j < edges.length; j++) {
const [u, v] = edges[j];
const logValue = Math.log(succProb[j]);
if (logProb[u] !== -Infinity && logProb[u] + logValue > logProb[v]) {
logProb[v] = logProb[u] + logValue;
updated = true;
}
if (logProb[v] !== -Infinity && logProb[v] + logValue > logProb[u]) {
logProb[u] = logProb[v] + logValue;
updated = true;
}
}
if (!updated) break;
}
return logProb[end] !== -Infinity ? Math.exp(logProb[end]) : 0;
}
}using System;
public class Solution {
public double MaxProbability(int n, int[][] edges, double[] succProb, int start, int end) {
double[] logProb = new double[n];
Array.Fill(logProb, double.NegativeInfinity);
logProb[start] = 0;
for (int i = 0; i < n - 1; i++) {
bool updated = false;
for (int j = 0; j < edges.Length; j++) {
int u = edges[j][0], v = edges[j][1];
double logValue = Math.Log(succProb[j]);
if (logProb[u] != double.NegativeInfinity && logProb[u] + logValue > logProb[v]) {
logProb[v] = logProb[u] + logValue;
updated = true;
}
if (logProb[v] != double.NegativeInfinity && logProb[v] + logValue > logProb[u]) {
logProb[u] = logProb[v] + logValue;
updated = true;
}
}
if (!updated) break;
}
return logProb[end] != double.NegativeInfinity ? Math.Exp(logProb[end]) : 0.0;
}
}This Python solution adapts the Bellman-Ford algorithm by carrying out edge relaxation iteratively, updating the path if a higher probability (converted to a lower negative log value) is discovered. It calculates the log-probability instead of direct product and converts back the resultant path strength using exponentiation. The algorithm stops early if no updates are performed in an iteration, indicating convergence to optimal.
Time Complexity: O(V * E), where V is the number of vertices and E is the number of edges in the graph, each edge potentially causing updates across V-1 iterations.
Space Complexity: O(V), for storing probability values and log-converted results for paths during processing.
Approach 3: Heap-Optimized Dijkstra Algorithm
We can use Dijkstra's algorithm to find the shortest path, but here we modify it slightly to find the path with the maximum probability.
We use a priority queue (max-heap) pq to store the probability from the starting point to each node and the node's identifier. Initially, we set the probability of the starting point to 1 and the probabilities of the other nodes to 0, then add the starting point to pq.
In each iteration, we take out the node a with the highest probability from pq and its probability w. If the probability of node a is already greater than w, we can skip this node. Otherwise, we traverse all adjacent edges (a, b) of a. If the probability of b is less than the probability of a multiplied by the probability of (a, b), we update the probability of b and add b to pq.
Finally, we obtain the maximum probability from the starting point to the endpoint.
The time complexity is O(m times log m), and the space complexity is O(m). Here, m is the number of edges.
function maxProbability(
n: number,
edges: number[][],
succProb: number[],
start_node: number,
end_node: number,
): number {
const pq = new PriorityQueue<number[]>((a, b) => b[0] - a[0]);
const g: [number, number][][] = Array.from({ length: n }, () => []);
for (let i = 0; i < edges.length; ++i) {
const [a, b] = edges[i];
g[a].push([b, succProb[i]]);
g[b].push([a, succProb[i]]);
}
const dist = Array.from({ length: n }, () => 0);
dist[start_node] = 1;
pq.enqueue([1, start_node]);
while (!pq.isEmpty()) {
const [w, a] = pq.dequeue();
if (dist[a] > w) {
continue;
}
for (const [b, p] of g[a]) {
const nw = w * p;
if (nw > dist[b]) {
dist[b] = nw;
pq.enqueue([nw, b]);
}
}
}
return dist[end_node];
}func maxProbability(n int, edges [][]int, succProb []float64, start_node int, end_node int) float64 {
g := make([][]pair, n)
for i, e := range edges {
a, b := e[0], e[1]
p := succProb[i]
g[a] = append(g[a], pair{p, b})
g[b] = append(g[b], pair{p, a})
}
pq := hp{{1, start_node}}
dist := make([]float64, n)
dist[start_node] = 1
for len(pq) > 0 {
p := heap.Pop(&pq).(pair)
w, a := p.p, p.a
if dist[a] > w {
continue
}
for _, e := range g[a] {
b, p := e.a, e.p
if nw := w * p; nw > dist[b] {
dist[b] = nw
heap.Push(&pq, pair{nw, b})
}
}
}
return dist[end_node]
}
type pair struct {
p float64
a int
}
type hp []pair
func (h hp) Len() int { return len(h) }
func (h hp) Less(i, j int) bool { return h[i].p > h[j].p }
func (h hp) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *hp) Push(x any) { *h = append(*h, x.(pair)) }
func (h *hp) Pop() (x any) { a := *h; x = a[len(a)-1]; *h = a[:len(a)-1]; return }Complexity comparison
| Approach | Complexity |
|---|---|
| Dijkstra's Algorithm with Maximum Product | Time Complexity: O(E log V), where E is the number of edges and V is the number of vertices, due to the use of the priority queue. |
| Bellman-Ford Algorithm | Time Complexity: O(V * E), where V is the number of vertices and E is the number of edges in the graph, each edge potentially causing updates across V-1 iterations. |
| Heap-Optimized Dijkstra Algorithm | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dijkstra's Algorithm with Max Heap | O(E log V) | O(V + E) | Best general solution for weighted graphs when maximizing probability |
| Bellman-Ford Algorithm | O(V * E) | O(V) | Useful when implementing simple edge relaxation without priority queue |
Frequently asked questions
Is Path with Maximum Probability easy or hard?
Path with Maximum Probability is rated Medium. The difficulty comes from recognizing that the problem is a modified shortest-path problem and adapting Dijkstra's algorithm to maximize probability instead of minimizing distance.
Path with Maximum Probability Python/Java solution
Most implementations use Dijkstra's algorithm with a priority queue. Python solutions typically use heapq with negative probabilities to simulate a max heap, while Java uses PriorityQueue with a custom comparator. Both maintain an array storing the maximum probability for each node.
How to solve Path with Maximum Probability in O(E log V)?
Construct an adjacency list for the graph and use a max heap priority queue. Start with probability 1.0 at the source node, then repeatedly extract the node with the highest probability. For each neighbor, update its probability if the product of the current probability and edge probability is greater than the stored value.
What is the best approach for Path with Maximum Probability?
Dijkstra's algorithm with a max heap is the best approach. Instead of minimizing distance, the algorithm maximizes the product of probabilities along edges. Each step selects the node with the highest current probability and relaxes its neighbors. The time complexity is O(E log V), which is efficient for sparse graphs.
Is Path with Maximum Probability asked at Google/Amazon/Meta?
Graph shortest-path variations like this frequently appear in interviews at companies such as Amazon, Google, and Meta. Interviewers often test whether candidates can adapt Dijkstra's algorithm to non-standard metrics such as probabilities or maximum products.
What data structure is used in Path with Maximum Probability?
The main data structures are an adjacency list to represent the graph and a max heap (priority queue) to select the next node with the highest probability. An array or hash structure tracks the best probability found so far for each node.
What is the time complexity of Path with Maximum Probability?
The optimal solution using Dijkstra's algorithm with a priority queue runs in O(E log V) time, where E is the number of edges and V is the number of nodes. The Bellman-Ford alternative runs in O(V * E) time because it relaxes all edges up to V-1 times.