Grokking Graph Algorithms for Coding Interviews
Ask Author
Back to course home

0% completed

Vote For New Content
Path with Maximum Probability (medium)
On this page

Problem Statement

Examples

Try it yourself

Problem Statement

You are given an undirected graph with n nodes labeled from 0 to n-1. The graph is described using an edge list, where each edge connects two 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.

The result should be accurate within a margin of 1e<sup>-5</sup>.

Examples

Example 1:

  • Input:
    • n = 5
    • edges = [[0, 1], [1, 2], [2, 4], [2, 3],[3, 4], [0, 4]]
    • succProb = [0.5, 0.5, 0.5, 0.5, 0.7, 0.1]
    • start = 0
    • end = 4
  • Expected Output: 0.125
Image
  • Justification: The direct path 0 -> 4 has a probability of 0.1, while another path (e.g., 0 -> 1 -> 2 -> 4) has a higher probability of 0.125.

Example 2:

  • Input:
    • n = 4
    • edges = [[0, 1], [1, 2], [2, 3], [0, 2]]
    • succProb = [0.5, 0.6, 0.7, 0.5]
    • start = 0
    • end = 3
  • Expected Output: 0.35
Image
  • Justification: The path 0 -> 2 -> 3 has the highest success probability (0.5 * 0.7 = 0.35).

Example 3:

  • Input:
    • n = 3
    • edges = [[0, 1], [1, 2]]
    • succProb = [0.9, 0.9]
    • start = 0
    • end = 2
  • Expected Output: 0.81
Image
  • Justification: The only path 0 -> 1 -> 2 has a success probability of 0.9 * 0.9 = 0.81.

Constraints:

  • 2 <= n <= 10<sup>4</sup>
  • 0 <= start, end < n
  • start != end
  • 0 <= a, b < n
  • a != b
  • 0 <= succProb.length == edges.length <= 2*10<sup>4</sup>
  • 0 <= succProb[i] <= 1
  • There is at most one edge between every two nodes.

Try it yourself

Try solving this question here:

Python3
Python3
. . . .

.....

.....

.....

Like the course? Get enrolled and start learning!

On this page

Problem Statement

Examples

Try it yourself