Tap here to switch tabs
Problem
Submissions

Problem: Path with Maximum Probability

Path with Maximum Probability asks you to navigate an undirected weighted graph from a start node to an end node, returning the highest possible success probability, or zero when no path exists.

Statement

You are given an undirected weighted graph of n nodes, represented by a 0-indexed list, edges, where edges[i] = [a, b] is an undirected edge connecting the nodes a and b. There is another list succProb, where succProb[i] is the probability of success of traversing the edge edges[i].

Additionally, you are given two nodes, start and end. Your task is to 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.

Constraints:

  • 2≤2 \leq n ≤103\leq 10^3

  • 0≤0 \leq start, end << n

  • start ≠\neq end

  • 0≤0 \leq a, b << n

  • a ≠\neq b

  • 0≤0 \leq succProb.length ==== edges.length ≤2×103\leq 2\times10^3

  • 0≤0 \leq succProb[i] ≤1\leq 1

  • There is, at most, one edge between every two nodes.

⋮
Tap here to switch tabs
Problem
Submissions

Problem: Path with Maximum Probability

Path with Maximum Probability asks you to navigate an undirected weighted graph from a start node to an end node, returning the highest possible success probability, or zero when no path exists.

Statement

You are given an undirected weighted graph of n nodes, represented by a 0-indexed list, edges, where edges[i] = [a, b] is an undirected edge connecting the nodes a and b. There is another list succProb, where succProb[i] is the probability of success of traversing the edge edges[i].

Additionally, you are given two nodes, start and end. Your task is to 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.

Constraints:

  • 2≤2 \leq n ≤103\leq 10^3

  • 0≤0 \leq start, end << n

  • start ≠\neq end

  • 0≤0 \leq a, b << n

  • a ≠\neq b

  • 0≤0 \leq succProb.length ==== edges.length ≤2×103\leq 2\times10^3

  • 0≤0 \leq succProb[i] ≤1\leq 1

  • There is, at most, one edge between every two nodes.