Most Reliable Path in a Probabilistic Graph

Problem You are given a graph representing a spider web. The spider starts at node S and wants to reach node T. Each edge e has a probability of breaking p(e) (0 <= p(e) <= 1). If an edge breaks, it cannot be used. Edge failures are independent. The spider chooses a path from S to T. The path succeeds if all edges on the path do not break. Compute: The maximum success probability from S to T. (Optional) One path achieving that maximum. Notes If the input gives breaking probability p(e), then edge success probability is q(e) = 1 - p(e). The path success probability is the product Π q(e). Constraints (interview-friendly) 1 <= n <= 2 * 10^5 0 <= m <= 3 * 10^5 assume an undirected graph unless specified otherwise. Design an efficient algorithm. Example Input n=3 edges=[[0,1],[1,2],[0,2]] breakP=[0.1,0.1,0.3] S=0 T=2 Output 0.81 path: 0 1 2