Show problems as
Classic problem #1514MediumArrayGraph TheoryHeap (Priority Queue)Shortest PathDijkstra's Algorithm

Path with Maximum Probability

Real-world version: Most Reliable Parcel Route
Tracked in this browser only
Read Path with Maximum Probability on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

Learn the pattern firstWith Graphs · Priority Queues, animated step by step

A courier company runs n depots, numbered 0 to n - 1, joined by two-way trunk links.

The links are given as two parallel arrays. links[i] = [u, v] is a link that a parcel may cross in either direction, and success[i] is the probability that a parcel crossing that link arrives undamaged. No pair of depots is joined by more than one link, and no link joins a depot to itself.

A route is a sequence of links leading from one depot to the next. A parcel survives the route only if it survives every link on it, and the links fail independently, so the route's success probability is the product of the success values of the links it uses.

Return the largest success probability of any route from depot origin to depot target. If no route joins them at all, return 0.0.

Report the probability as a decimal number; an answer within 1e-5 of the correct value is accepted.

Examples

Example 1

Input
n = 4, links = [[0,1],[1,3],[0,2],[2,3]], success = [0.5,0.75,0.875,0.25], origin = 0, target = 3
Output
0.375

The route 0 to 1 to 3 uses the links with chances 0.5 and 0.75, so a parcel survives it with probability 0.5 * 0.75 = 0.375. The other route, 0 to 2 to 3, multiplies out to 0.875 * 0.25 = 0.21875.

Example 2

Input
n = 5, links = [[0,1],[1,2],[3,4]], success = [0.5,0.5,1.0], origin = 0, target = 4
Output
0.0

Depots 0, 1 and 2 sit on one side and depots 3 and 4 on the other, with no link crossing between the two sides, so no route reaches depot 4 from depot 0.

Example 3

Input
n = 2, links = [[0,1]], success = [0.625], origin = 1, target = 0
Output
0.625

The single link is written as [0,1] but may be crossed in either direction, so the one-link route from depot 1 to depot 0 carries its chance of 0.625.

Constraints

  • 2 <= n <= 10^4
  • 0 <= links.length <= 2 * 10^4
  • links.length == success.length
  • links[i].length == 2
  • 0 <= links[i][j] <= n - 1
  • links[i][0] != links[i][1]
  • 0 <= success[i] <= 1
  • 0 <= origin <= n - 1
  • 0 <= target <= n - 1
  • origin != target
  • At most one link joins any given pair of depots.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def best_delivery_odds(n: int, links: list[list[int]], success: list[float], origin: int, target: int) -> float:
Java
public double bestDeliveryOdds(int n, int[][] links, double[] success, int origin, int target)

More on the same topics