Medium

Path with Maximum Probability

071

Given weighted undirected edges and start/end nodes, return the maximum success probability.

EXAMPLES

Example 1

Input
{
  "n": 3,
  "edges": [
    [
      0,
      1
    ],
    [
      1,
      2
    ],
    [
      0,
      2
    ]
  ],
  "probabilityPercent": [
    50,
    50,
    20
  ],
  "start": 0,
  "end": 2
}

Output
0.25

FUNCTION SHAPE

n: intedges: intMatrixprobabilityPercent: intArraystart: intend: int→double

SOLUTION NOTE

Pretty standard, just know that we are instead using max path, and we continue the path through multiplication rather than addition of weights.

But wait, dijkstras only works for min paths? You are right. If you use dijkstras to find max paths, it won't work because that is NP complete. The only reason this works is because it is multiplication rather than addition. Let's explain:

Let's say the optimal path P = p1*...*pk
Since log(x) is mono increasing, max P has the same max path as max log(P), and max P is the same as min -logP.
Property of log gives: -logP = -logp1 - …. - logpk.

This means, max P is the same as min the sum of -log of the edge weights. Also, since 0 <= pi <= 1, that means log(pi) <= 0 and -log(pi) >= 0, so we have non-negative edge weights.

What this means, is dijkstras will find the max path P on the -log of the edge weights. We note that we don't take the log of the edge weights in the code, because we showed that the max P problem is the same as min -logP, meaning it is correct, and we can use either approach to solve this problem.

Reveal reference solution +

pythonREFERENCE

# dijkstra
def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start: int, end: int) -> float:
    heap = [(-1, start)] # max heap

    adjList = defaultdict(list)
    for (u,v),w in zip(edges, succProb):
        adjList[u].append((v,w))
        adjList[v].append((u,w))
    p = defaultdict(int)
    p[start] = 1 # all other p[i] are init to 0, as desired.

    while heap:
        prob, curr = heappop(heap)
        prob = - prob

        if curr == end: return prob

        if p[curr] > prob: continue # no point, already visited a larger prob path through curr.
        assert(p[curr] == prob)

        for nbr,w in adjList[curr]:
            if prob * w > p[nbr]:
                p[nbr] = prob * w
                heappush(heap, (- p[nbr], nbr))

    return 0

TimeO((V+E)log V)

SpaceO(V+E)

Open on LeetCode ↗