• Justification: The only path 0 -> 1 -> 2 has a success probability of 0.9 * 0.9 = 0.81.

Constraints:

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

Solution

To solve this problem, we will use Dijkstra's algorithm, typically used for finding the shortest path in weighted graphs. However, instead of summing the weights, we'll multiply the probabilities to find the maximum product path.

This approach is effective because it ensures that we explore all possible paths from the starting node and select the path that yields the highest success probability. Using a priority queue, we can efficiently track the highest probability paths and update them as we explore the graph.

Step-by-Step Algorithm

1. Initialization:

   • Create an adjacency list graph to represent the graph. Each node points to a list of edges, where each edge is a pair (neighbor, probability).
   • Initialize a max-heap (priority queue) to keep track of the nodes to explore. This heap stores pairs (probability, node), sorted by probability in descending order.
   • Create an array probabilities to store the maximum probability of reaching each node from the start node. Initialize this array with zeros and set the start node's probability to 1.0.

2. Graph Construction:

   • Iterate through each edge in the input edges list.
   • For each edge (u, v) with probability p, add (v, p) to the adjacency list of u and (u, p) to the adjacency list of v.

3. Dijkstra's Algorithm with Probability:

   • Push the start node with probability 1.0 into the max-heap.
   • While the max-heap is not empty:
     • Pop the node with the highest probability from the heap. Let this be current_node with current_prob.
     • If current_node is the end node, return current_prob as the result.
     • For each neighbor of current_node:
       • Calculate the new probability to reach this neighbor as current_prob * edge_prob.
       • If the new probability is greater than the currently known probability to reach this neighbor, update the probabilities array and push the neighbor with the new probability into the max-heap.

4. Result:

   • If the heap is exhausted and the end node is not reached, return 0.0.

Algorithm Walkthrough

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

Steps:

1. Initialization:

   • graph = {0: [], 1: [], 2: [], 3: [], 4: []}
   • maxHeap = []
   • probabilities = [1.0, 0.0, 0.0, 0.0, 0.0]

2. Graph Construction:

   • Final graph:

     {
       0: [(1, 0.5), (4, 0.1)],
       1: [(0, 0.5), (2, 0.5)],
       2: [(1, 0.5), (4, 0.5), (3, 0.5)],
       3: [(2, 0.5), (4, 0.7)],
       4: [(2, 0.5), (3, 0.7), (0, 0.1)]
     }
     

3. Dijkstra's Algorithm with Probability:

   • Push start node:
     • maxHeap.push((0, 1.0))
     • maxHeap = [(0, 1.0)]
   • Iteration 1:
     • Pop node 0 with prob 1.0:
       • current_node = 0
       • current_prob = 1.0
       • maxHeap = []
     • Check neighbors of node 0:
       • Neighbor 1 with edge prob 0.5:
         • New prob = 1.0 * 0.5 = 0.5
         • Update prob of node 1: probabilities[1] = 0.5
         • Push (1, 0.5) to heap:
           • maxHeap.push((1, 0.5))
           • maxHeap = [(1, 0.5)]
       • Neighbor 4 with edge prob 0.1:
         • New prob = 1.0 * 0.1 = 0.1
         • Update prob of node 4: probabilities[4] = 0.1
         • Push (4, 0.1) to heap:
           • maxHeap.push((4, 0.1))
           • maxHeap = [(1, 0.5), (4, 0.1)]
   • Iteration 2:
     • Pop node 1 with prob 0.5:
       • current_node = 1
       • current_prob = 0.5
       • maxHeap = [(4, 0.1)]
     • Check neighbors of node 1:
       • Neighbor 0 with edge prob 0.5 (new prob = 0.5 * 0.5 = 0.25, no update needed)
       • Neighbor 2 with edge prob 0.5:
         • New prob = 0.5 * 0.5 = 0.25
         • Update prob of node 2: probabilities[2] = 0.25
         • Push (2, 0.25) to heap:
           • maxHeap.push((2, 0.25))
           • maxHeap = [(2, 0.25), (4, 0.1)]
   • Iteration 3:
     • Pop node 2 with prob 0.25:
       • current_node = 2
       • current_prob = 0.25
       • maxHeap = [(4, 0.1)]
     • Check neighbors of node 2:
       • Neighbor 1 with edge prob 0.5 (new prob = 0.25 * 0.5 = 0.125, no update needed)
       • Neighbor 4 with edge prob 0.5:
         • New prob = 0.25 * 0.5 = 0.125
         • Update prob of node 4: probabilities[4] = 0.125
         • Push (4, 0.125) to heap:
           • maxHeap.push((4, 0.125))
           • maxHeap = [(4, 0.125), (4, 0.1)]
       • Neighbor 3 with edge prob 0.5:
         • New prob = 0.25 * 0.5 = 0.125
         • Update prob of node 3: probabilities[3] = 0.125
         • Push (3, 0.125) to heap:
           • maxHeap.push((3, 0.125))
           • maxHeap = [(4, 0.125), (4, 0.1), (3, 0.125)]
   • Iteration 4:
     • Pop node 4 with prob 0.125:
       • current_node = 4
       • current_prob = 0.125
       • maxHeap = [(3, 0.125), (4, 0.1)]
     • Node 4 is the end node, return 0.125.

Code