Problem Description

The "Path with Maximum Probability" problem asks you to find the path between two nodes in an undirected graph that yields the highest probability, given the probabilities of successfully traversing each edge.

You are given:

• An integer n representing the number of nodes (labeled 0 to n - 1).
• A 2D array edges where each element [a, b] represents an undirected edge between nodes a and b.
• An array succProb where succProb[i] is the success probability of traversing edge edges[i].
• Two integers start and end representing the start and end nodes.

• Each edge can only be used once per path.
• There may be multiple paths; we want the one with the highest probability.
• Probabilities are floating-point numbers between 0 and 1.

Thought Process

At first glance, this problem resembles the classic shortest path problem in graphs (like Dijkstra's algorithm), but instead of minimizing sum of weights, we are maximizing the product of probabilities.

One brute-force approach would be to try every possible path from start to end, calculate the product for each, and return the maximum. However, this is computationally infeasible for large graphs, as the number of paths can grow exponentially.

Instead, we need a way to efficiently explore the graph, always keeping track of the best (highest probability) path to each node. This suggests using a priority queue (or heap), similar to Dijkstra's, but with the goal of maximizing the product, not minimizing the sum.

The conceptual shift is from "shortest sum of weights" to "maximum product of weights," but the greedy exploration principle remains the same.

Solution Approach

We use a modified version of Dijkstra's algorithm to solve this problem. Here’s how:

1. Graph Representation:
   • We use an adjacency list (e.g., a hash map or array of lists) to represent the graph, where each node points to its neighbors and the probability of the connecting edge.
2. Priority Queue:
   • We use a max-heap (priority queue) to always process the node with the current highest probability path.
3. Probability Tracking:
   • We maintain an array (or map) to store the highest probability found so far for each node.
4. Algorithm Steps:
   • Initialize the heap with the start node and probability 1.0 (since we start there).
   • While the heap is not empty:
     • Pop the node with the highest probability.
     • If it's the end node, return its probability—this is the maximum possible.
     • For each neighbor, calculate the new probability (current prob × edge prob).
     • If this new probability is higher than the previously recorded one for that neighbor, update it and push the neighbor into the heap.
   • If the end node is never reached, return 0.
5. Why This Works:
   • We always process the most promising (highest probability) path first, ensuring the first time we reach end is with the max probability.

Example Walkthrough

Sample Input:
n = 3
edges = [[0,1],[1,2],[0,2]]
succProb = [0.5, 0.5, 0.2]
start = 0
end = 2

Graph:

• Edge 0-1: 0.5
• Edge 1-2: 0.5
• Edge 0-2: 0.2

• Start at node 0, probability = 1.0
• From 0, can go to 1 (prob = 1.0 × 0.5 = 0.5) and 2 (prob = 1.0 × 0.2 = 0.2)
• Heap: [(0.5, 1), (0.2, 2)]
• Pop (0.5, 1). From 1, can go to 2 (prob = 0.5 × 0.5 = 0.25)
• Heap: [(0.25, 2), (0.2, 2)]
• Pop (0.25, 2). Node 2 is the end node. Return 0.25.

Time and Space Complexity

Brute-force Approach:

• Time: Exponential, O(2^n) in the worst case due to all possible paths.
• Space: Also exponential due to recursion stack or path storage.

• Time: O(E log N), where E is the number of edges and N is the number of nodes. Each edge may be processed once for each node, and heap operations are log N.
• Space: O(N + E) for the graph and probability storage.

Summary

To solve the "Path with Maximum Probability" problem, we adapt Dijkstra's algorithm to maximize the product of probabilities instead of minimizing the sum of weights. By using a priority queue and always expanding the most promising node, we efficiently find the optimal path. The key insight is that the greedy approach still applies when maximizing products, and by keeping track of the best probability for each node, we avoid unnecessary computations.

Code Implementation

import heapq
from collections import defaultdict

class Solution:
    def maxProbability(self, n, edges, succProb, start, end):
        graph = defaultdict(list)
        for (a, b), prob in zip(edges, succProb):
            graph[a].append((b, prob))
            graph[b].append((a, prob))
        
        maxProb = [0.0] * n
        maxProb[start] = 1.0
        heap = [(-1.0, start)]  # use negative for max-heap

        while heap:
            prob, node = heapq.heappop(heap)
            prob = -prob
            if node == end:
                return prob
            for neighbor, edgeProb in graph[node]:
                newProb = prob * edgeProb
                if newProb > maxProb[neighbor]:
                    maxProb[neighbor] = newProb
                    heapq.heappush(heap, (-newProb, neighbor))
        return 0.0
      

#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 a = edges[i][0], b = edges[i][1];
            double p = succProb[i];
            graph[a].push_back({b, p});
            graph[b].push_back({a, p});
        }
        vector<double> maxProb(n, 0.0);
        maxProb[start] = 1.0;
        priority_queue<pair<double, int>> pq;
        pq.push({1.0, start});

        while (!pq.empty()) {
            auto [prob, node] = pq.top();
            pq.pop();
            if (node == end) return prob;
            for (auto& [neighbor, edgeProb] : graph[node]) {
                double newProb = prob * edgeProb;
                if (newProb > maxProb[neighbor]) {
                    maxProb[neighbor] = newProb;
                    pq.push({newProb, neighbor});
                }
            }
        }
        return 0.0;
    }
};
      

import java.util.*;

class Solution {
    public double maxProbability(int n, int[][] edges, double[] succProb, int start, int end) {
        List<List<double[]>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) graph.add(new ArrayList<>());
        for (int i = 0; i < edges.length; i++) {
            int a = edges[i][0], b = edges[i][1];
            double p = succProb[i];
            graph.get(a).add(new double[]{b, p});
            graph.get(b).add(new double[]{a, p});
        }
        double[] maxProb = new double[n];
        maxProb[start] = 1.0;
        PriorityQueue<double[]> pq = new PriorityQueue<>((a, b) -> Double.compare(b[0], a[0]));
        pq.offer(new double[]{1.0, start});

        while (!pq.isEmpty()) {
            double[] curr = pq.poll();
            double prob = curr[0];
            int node = (int)curr[1];
            if (node == end) return prob;
            for (double[] neighbor : graph.get(node)) {
                int next = (int)neighbor[0];
                double edgeProb = neighbor[1];
                double newProb = prob * edgeProb;
                if (newProb > maxProb[next]) {
                    maxProb[next] = newProb;
                    pq.offer(new double[]{newProb, next});
                }
            }
        }
        return 0.0;
    }
}
      

/**
 * @param {number} n
 * @param {number[][]} edges
 * @param {number[]} succProb
 * @param {number} start
 * @param {number} end
 * @return {number}
 */
function maxProbability(n, edges, succProb, start, end) {
    const graph = Array.from({length: n}, () => []);
    for (let i = 0; i < edges.length; i++) {
        const [a, b] = edges[i];
        const p = succProb[i];
        graph[a].push([b, p]);
        graph[b].push([a, p]);
    }
    const maxProb = Array(n).fill(0);
    maxProb[start] = 1.0;
    // Max heap using array and sort (for small N, or use PriorityQueue lib)
    let heap = [[1.0, start]];
    while (heap.length) {
        heap.sort((a, b) => b[0] - a[0]);
        const [prob, node] = heap.shift();
        if (node === end) return prob;
        for (const [neighbor, edgeProb] of graph[node]) {
            const newProb = prob * edgeProb;
            if (newProb > maxProb[neighbor]) {
                maxProb[neighbor] = newProb;
                heap.push([newProb, neighbor]);
            }
        }
    }
    return 0.0;
}