Path with Maximum Probability

Path with Maximum Probability is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Graph Traversal Patterns (DFS & BFS) pattern, in the Shortest Path (Dijkstra's Algorithm) subpattern.

Problem statement

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^4

- 0 <= start, end < n

- start != end

- 0 <= a, b < n

- a != b

- 0 <= succProb.length == edges.length <= 210^4

- 0 <= succProb[i] <= 1

- There is at most one edge between every two nodes.

Topics and companies

Topics: Array, Graph, Heap (Priority Queue), Shortest Path.

Reported in interviews at Google.

How to practise Path with Maximum Probability on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(M log N), where M = number of edges and N = number of nodes. Each edge can be relaxed at most once, and each heap operation is O(log N). time and O(M + N), for the adjacency list (O(M)) and the maxProb array (O(N)), plus the priority queue (up to O(N)). space.

Open Path with Maximum Probability in the code editor, or read the Path with Maximum Probability editorial for a worked solution with its approach and complexity analysis.

Where Path with Maximum Probability sits in the DSA pattern sheet

Problems related to Path with Maximum Probability

Other problems that use the same Shortest Path (Dijkstra's Algorithm) and Graph Traversal Patterns (DFS & BFS) techniques:

Preparing this workspace.