1514. Path with Maximum Probability

Array Dynamic Programming Graph Heap (Priority Queue)Shortest Path Probability & Statistics

Problem Overview

Find the path from src to dst with maximum probability product.

Intuition

Find the path from src to dst with maximum probability product. This is shortest-path with weights inverted — use Dijkstra on negative log probabilities, or a max-heap that always expands the most promising partial path first.

Algorithm

1Build adjacency list: each edge (u,v,p) adds (v,p) to u and (u,p) to v.
2Initialize prob[src] = 1.0, others 0. Max-priority queue by probability.
3Pop highest-prob node u. For each neighbor v with edge prob w:
4newProb = prob[u] * w. If newProb > prob[v], update prob[v] and push v.
5Return prob[dst] when done (or when dst is popped).

Example Walkthrough

Input: n=3, edges=[[0,1,0.5],[1,2,0.5],[0,2,0.2]], src=0, dst=2

1.Path 0->1->2: 0.5*0.5 = 0.25 beats direct 0->2 at 0.2.

Output: 0.25

Common Pitfalls

•Multiply probabilities — do not add edge weights like distance Dijkstra.
•Use max-heap, not min-heap.
•Floating point is fine; compare with epsilon if needed on some platforms.

1514.cs

// Approach: Modified Dijkstra with a max-heap; propagate maximum probability along edges.
// Time: O((V+E) log V) Space: O(V+E)

public class Solution
        // {a: [(b, probability_ab)]}
        List<(int, double)>[] graph = new List<(int, double)>[n];
        // (the probability to reach u, u)
        PriorityQueue<(double, int), double> maxHeap = new PriorityQueue<(double, int), double>(new MaxHeapComparer());

        maxHeap.Enqueue((1.0, start_node), 1.0);
        bool[] seen = new bool[n];

        for (int i = 0; i < n; ++i)
            graph[i] = new List<(int, double)>();

        for (int i = 0; i < edges.Length; ++i)
        {
            int u = edges[i][0];
            int v = edges[i][1];
            double prob = succProb[i];
            graph[u].Add((v, prob));
            graph[v].Add((u, prob));
        }

        while (maxHeap.Count > 0)
        {
            var (prob, u) = maxHeap.Dequeue();
            if (u == end_node)
                return prob;
            if (seen[u])
                continue;
            seen[u] = true;
            foreach (var node in graph[u])
            {
                int nextNode = node.Item1;
                double edgeProb = node.Item2;
                if (seen[nextNode])
                    continue;
                maxHeap.Enqueue((prob * edgeProb, nextNode), prob * edgeProb);
            }
        }

        return 0;
    }

    public class MaxHeapComparer : IComparer<double>
    {
        public int Compare(double a, double b)
        {
            return b.CompareTo(a);
        }
    }
}

Was this solution helpful?