# Path with Maximum Probability
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/path-with-maximum-probability)
Canonical: https://scaleengineer.com/dsa/problems/path-with-maximum-probability
**Algorithms:** [Shortest Path](https://scaleengineer.com/algorithms/shortest-path)
**Data structures:** Array, Heap (Priority Queue), Graph
**Companies:** [tcs](https://scaleengineer.com/companies/tcs), [BlackRock](https://scaleengineer.com/companies/blackrock)
---
## 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:**

**![](https://assets.glich.co/dsa/path-with-maximum-probability/image0.png)**

**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:**

**![](https://assets.glich.co/dsa/path-with-maximum-probability/image1.png)**

**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:**

**![](https://assets.glich.co/dsa/path-with-maximum-probability/image2.png)**

**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.

# Approaches
## Bellman-Ford Algorithm Modification
This approach adapts the Bellman-Ford algorithm, which is typically used for finding the shortest paths in a weighted graph, even with negative edge weights. Instead of minimizing the sum of edge weights, we modify it to maximize the product of probabilities. The Bellman-Ford algorithm works by iteratively "relaxing" edges. In our modification, a relaxation step involves checking if traversing an edge can lead to a path with a higher total probability to a node and updating it if so.
**Time:** O(n * E), where `n` is the number of nodes and `E` is the number of edges. The algorithm has a main loop that runs `n-1` times, and inside this loop, it iterates through all `E` edges. · **Space:** O(n), where `n` is the number of nodes. This is for the `maxProb` array used to store the maximum probabilities to each node.
**Pros:** Relatively simple to understand and implement without complex data structures like priority queues.; It can handle all types of graphs, including those that would have negative cycles in a standard shortest-path context (though not relevant here).
**Cons:** The time complexity of O(n * E) is generally too slow for graphs of the size specified in the constraints, and it will likely result in a 'Time Limit Exceeded' error.
### Explanation
We maintain an array, `maxProb`, of size `n`, where `maxProb[i]` stores the maximum probability of a path from the `start` node to node `i`. We initialize `maxProb[start]` to 1.0 and all other entries to 0.0, as we have a 100% chance of being at the start initially and zero chance of being anywhere else.

The algorithm then iterates `n-1` times. In each iteration, it processes all `E` edges of the graph. For each edge `(u, v)` with success probability `p`, it updates the probability to reach `v` if the path through `u` (`maxProb[u] * p`) is better than the current known probability `maxProb[v]`. Since the graph is undirected, the same update is considered for `u` via `v`. This process is repeated `n-1` times to guarantee that the maximum probabilities for paths of all possible lengths (up to `n-1` edges) are found. After the iterations, `maxProb[end]` will hold the solution.

```java
class Solution {
    public double maxProbability(int n, int[][] edges, double[] succProb, int start, int end) {
        double[] maxProb = new double[n];
        maxProb[start] = 1.0;

        // Bellman-Ford requires n-1 iterations in the worst case.
        for (int i = 0; i < n - 1; i++) {
            boolean hasUpdate = false;
            for (int j = 0; j < edges.length; j++) {
                int u = edges[j][0];
                int v = edges[j][1];
                double prob = succProb[j];

                if (maxProb[u] * prob > maxProb[v]) {
                    maxProb[v] = maxProb[u] * prob;
                    hasUpdate = true;
                }
                if (maxProb[v] * prob > maxProb[u]) {
                    maxProb[u] = maxProb[v] * prob;
                    hasUpdate = true;
                }
            }
            // Optimization: if no updates in an iteration, we can stop early.
            if (!hasUpdate) {
                break;
            }
        }

        return maxProb[end];
    }
}
```
### Algorithm
*   Initialize a `double` array `maxProb` of size `n` with all values as 0.0.
*   Set `maxProb[start] = 1.0`.
*   Repeat the following steps `n-1` times:
    *   Create a flag `hasUpdate` and set it to `false`.
    *   Iterate through each edge `(u, v)` with probability `p`.
    *   If a more probable path to `v` is found via `u` (i.e., `maxProb[u] * p > maxProb[v]`), update `maxProb[v] = maxProb[u] * p` and set `hasUpdate` to `true`.
    *   Since the graph is undirected, do the same for the other direction: if `maxProb[v] * p > maxProb[u]`, update `maxProb[u] = maxProb[v] * p` and set `hasUpdate` to `true`.
    *   If after a full iteration over all edges, `hasUpdate` is `false`, it means no probabilities were improved, and we can break the loop early.
*   After the loops complete, `maxProb[end]` contains the maximum probability. Return this value.

## Dijkstra's Algorithm Modification
This problem can be solved efficiently by adapting Dijkstra's algorithm. Standard Dijkstra's finds the shortest path by minimizing a sum of weights. Here, we need to maximize a product of probabilities. We can modify the algorithm to achieve this by using a max-priority queue instead of a min-priority queue. This greedy approach ensures that we always explore the path that is currently the most probable, which is guaranteed to find the optimal solution because all edge 'weights' (probabilities) are positive, analogous to non-negative weights in the standard algorithm.

An alternative but equivalent method is to transform the problem. Maximizing a product `p1 * p2 * ...` is the same as maximizing its logarithm `log(p1) + log(p2) + ...`. This, in turn, is equivalent to minimizing the sum of negative logarithms `(-log(p1)) + (-log(p2)) + ...`. Since probabilities are `≤ 1`, their logs are `≤ 0`, and their negative logs are `≥ 0`. This transforms the problem into a standard shortest path problem with non-negative weights, solvable by the classic Dijkstra's algorithm. The implementation below uses the direct maximization approach for simplicity.
**Time:** O(E log n), where `n` is the number of nodes and `E` is the number of edges. Building the adjacency list takes O(E). The main loop processes each node and edge once. Each priority queue operation (insertion and extraction) takes O(log n) time. In the worst case, we perform one extraction per node and one insertion per edge. · **Space:** O(n + E), where `n` is the number of nodes and `E` is the number of edges. This space is used for the adjacency list O(E), the `maxProb` array O(n), and the priority queue, which can hold up to O(n) nodes in the worst case.
**Pros:** Highly efficient and the standard algorithm for this type of problem.; Guaranteed to find the optimal path because the problem structure (multiplying probabilities between 0 and 1) is analogous to summing non-negative weights.
**Cons:** Slightly more complex to implement than the Bellman-Ford approach due to the need for an adjacency list and a priority queue.
### Explanation
The core of this approach is to use a max-priority queue to greedily explore the most promising paths. We start at the `start` node with a probability of 1.

First, we represent the graph using an adjacency list for efficient access to neighbors. Then, we initialize an array `maxProb` to keep track of the maximum probability to reach each node from `start`, setting `maxProb[start]` to 1 and all others to 0.

We push the starting node and its probability `(1.0, start)` into a max-priority queue. The algorithm proceeds by repeatedly extracting the node with the highest probability from the queue. For the extracted node, we examine all its neighbors. For each neighbor, we calculate the probability of reaching it via the current node. If this new probability is higher than the previously recorded maximum probability for that neighbor, we update the `maxProb` array and push the neighbor with its new, higher probability into the queue.

We also include a check to discard stale entries from the queue—if we pull a node from the queue whose probability is already lower than what's in our `maxProb` array, we ignore it. The algorithm terminates when we extract the `end` node from the queue, as the greedy nature of Dijkstra's ensures this is the highest probability path.

```java
import java.util.*;

class Solution {
    public double maxProbability(int n, int[][] edges, double[] succProb, int start, int end) {
        // Adjacency list: Map<Node, List<Pair<Neighbor, Probability>>>
        Map<Integer, List<double[]>> adj = new HashMap<>();
        for (int i = 0; i < edges.length; i++) {
            int u = edges[i][0];
            int v = edges[i][1];
            double prob = succProb[i];
            adj.computeIfAbsent(u, k -> new ArrayList<>()).add(new double[]{v, prob});
            adj.computeIfAbsent(v, k -> new ArrayList<>()).add(new double[]{u, prob});
        }

        double[] maxProb = new double[n];
        maxProb[start] = 1.0;

        // Max-priority queue: {probability, node}
        PriorityQueue<double[]> pq = new PriorityQueue<>((a, b) -> Double.compare(b[0], a[0]));
        pq.offer(new double[]{1.0, (double)start});

        while (!pq.isEmpty()) {
            double[] current = pq.poll();
            double currentProb = current[0];
            int currentNode = (int)current[1];

            if (currentNode == end) {
                return currentProb;
            }
            
            if (currentProb < maxProb[currentNode]) {
                continue;
            }

            if (!adj.containsKey(currentNode)) {
                continue;
            }

            for (double[] neighbor : adj.get(currentNode)) {
                int neighborNode = (int)neighbor[0];
                double edgeProb = neighbor[1];
                double newProb = currentProb * edgeProb;

                if (newProb > maxProb[neighborNode]) {
                    maxProb[neighborNode] = newProb;
                    pq.offer(new double[]{newProb, (double)neighborNode});
                }
            }
        }

        return 0.0; // end is not reachable
    }
}
```
### Algorithm
*   Build an adjacency list representation of the graph where `adj[u]` contains a list of pairs `(v, p)`, representing an edge from `u` to `v` with probability `p`.
*   Initialize a `double` array `maxProb` of size `n` with all values as 0.0. Set `maxProb[start] = 1.0`.
*   Create a max-priority queue that stores pairs of `(probability, node)` and orders them by probability in descending order.
*   Add the starting pair `(1.0, start)` to the priority queue.
*   While the priority queue is not empty:
    *   Extract the pair `(currentProb, currentNode)` with the highest probability.
    *   If `currentNode` is the `end` node, we have found the optimal path, so return `currentProb`.
    *   If `currentProb` is less than `maxProb[currentNode]`, it means we've found a better path to this node already, so we skip this (stale) entry.
    *   For each neighbor `neighborNode` of `currentNode` with edge probability `edgeProb`:
        *   Calculate the probability of the path through `currentNode`: `newProb = currentProb * edgeProb`.
        *   If `newProb` is greater than `maxProb[neighborNode]`, we have found a better path. Update `maxProb[neighborNode] = newProb` and add the new pair `(newProb, neighborNode)` to the priority queue.
*   If the loop finishes and the `end` node has not been reached, it is unreachable. Return 0.0.

# Solutions
### Java

```java
class Solution {
public
  double maxProbability(int n, int[][] edges, double[] succProb, int start,
                        int end) {
    List<Pair<Integer, Double>>[] g = new List[n];
    Arrays.setAll(g, k->new ArrayList<>());
    for (int i = 0; i < edges.length; ++i) {
      int a = edges[i][0], b = edges[i][1];
      double s = succProb[i];
      g[a].add(new Pair<>(b, s));
      g[b].add(new Pair<>(a, s));
    }
    PriorityQueue<Pair<Double, Integer>> q =
        new PriorityQueue<>(Comparator.comparingDouble(Pair : : getKey));
    double[] d = new double[n];
    d[start] = 1.0;
    q.offer(new Pair<>(-1.0, start));
    while (!q.isEmpty()) {
      Pair<Double, Integer> p = q.poll();
      double w = p.getKey();
      w *= -1;
      int u = p.getValue();
      for (Pair<Integer, Double> ne : g[u]) {
        int v = ne.getKey();
        double t = ne.getValue();
        if (d[v] < d[u] * t) {
          d[v] = d[u] * t;
          q.offer(new Pair<>(-d[v], v));
        }
      }
    }
    return d[end];
  }
}

```

### CPP

```cpp
class Solution {
public:
  double maxProbability(int n, vector<vector<int>> &edges,
                        vector<double> &succProb, int start, int end) {
    vector<vector<pair<int, double>>> g(n);
    for (int i = 0; i < edges.size(); ++i) {
      int a = edges[i][0], b = edges[i][1];
      double s = succProb[i];
      g[a].push_back({b, s});
      g[b].push_back({a, s});
    }
    vector<double> d(n);
    d[start] = 1.0;
    queue<pair<double, int>> q;
    q.push({1.0, start});
    while (!q.empty()) {
      auto p = q.front();
      q.pop();
      double w = p.first;
      int u = p.second;
      if (d[u] > w)
        continue;
      for (auto &e : g[u]) {
        int v = e.first;
        double t = e.second;
        if (d[v] < d[u] * t) {
          d[v] = d[u] * t;
          q.push({d[v], v});
        }
      }
    }
    return d[end];
  }
};

```

### Python

```python
class Solution:
    def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start: int, end: int, ) -> float: g = defaultdict(list) for (a, b), s in zip(edges, succProb): g[a]. append((b, s)) g[b]. append((a, s)) q = [(- 1, start)] d = [0] * n d[start] = 1 while q: w, u = heappop(q) w = - w if d[u] > w: continue for v, t in g[u]: if d[v] < d[u] * t: d[v] = d[u] * t heappush(q, (- d[v], v)) return d[end]

```