<p>You are given an undirected weighted graph of&nbsp;<code>n</code>&nbsp;nodes (0-indexed), represented by an edge list where&nbsp;<code>edges[i] = [a, b]</code>&nbsp;is an undirected edge connecting the nodes&nbsp;<code>a</code>&nbsp;and&nbsp;<code>b</code>&nbsp;with a probability of success of traversing that edge&nbsp;<code>succProb[i]</code>.</p>

<p>Given two nodes&nbsp;<code>start</code>&nbsp;and&nbsp;<code>end</code>, find the path with the maximum probability of success to go from&nbsp;<code>start</code>&nbsp;to&nbsp;<code>end</code>&nbsp;and return its success probability.</p>

<p>If there is no path from&nbsp;<code>start</code>&nbsp;to&nbsp;<code>end</code>, <strong>return&nbsp;0</strong>. Your answer will be accepted if it differs from the correct answer by at most <strong>1e-5</strong>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<p><strong><img alt="" src="https://assets.leetcode.com/uploads/2019/09/20/1558_ex1.png" style="width: 187px; height: 186px;" /></strong></p>

<pre>
<strong>Input:</strong> n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.2], start = 0, end = 2
<strong>Output:</strong> 0.25000
<strong>Explanation:</strong>&nbsp;There are two paths from start to end, one having a probability of success = 0.2 and the other has 0.5 * 0.5 = 0.25.
</pre>

<p><strong class="example">Example 2:</strong></p>

<p><strong><img alt="" src="https://assets.leetcode.com/uploads/2019/09/20/1558_ex2.png" style="width: 189px; height: 186px;" /></strong></p>

<pre>
<strong>Input:</strong> n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.3], start = 0, end = 2
<strong>Output:</strong> 0.30000
</pre>

<p><strong class="example">Example 3:</strong></p>

<p><strong><img alt="" src="https://assets.leetcode.com/uploads/2019/09/20/1558_ex3.png" style="width: 215px; height: 191px;" /></strong></p>

<pre>
<strong>Input:</strong> n = 3, edges = [[0,1]], succProb = [0.5], start = 0, end = 2
<strong>Output:</strong> 0.00000
<strong>Explanation:</strong>&nbsp;There is no path between 0 and 2.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>2 &lt;= n &lt;= 10^4</code></li>
	<li><code>0 &lt;= start, end &lt; n</code></li>
	<li><code>start != end</code></li>
	<li><code>0 &lt;= a, b &lt; n</code></li>
	<li><code>a != b</code></li>
	<li><code>0 &lt;= succProb.length == edges.length &lt;= 2*10^4</code></li>
	<li><code>0 &lt;= succProb[i] &lt;= 1</code></li>
	<li>There is at most one edge between every two nodes.</li>
</ul>

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

Given two nodes start and end, 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. Your answer will 
be accepted if it differs from the correct answer by at most 1e-5.
"""

class Solution:
    def maxProbability(self, 
    n: int, 
    edges: List[List[int]], 
    succProb: List[float], 
    start_node: int, 
    end_node: int) -> float:
        
        """
        Dijkstra's path algorithm
        We have a state that keeps track of the max probability to 
        reach that node from the start node

        This can be an array

        Initially set the probability of visiting current node to 1 and all other nodes
        as 0

        Have a priority queue to decide which node to process first
        Add the start node to the priority queue with a probability of 1

        Then pick all the neighboring node
        And update it's probability - increase it , if currentProb * prob of edge is 
        Greater than the current probability in the initial array

        If so update it, else don't update

        Then we add this node to the priority queue for later processing if this isn't 
        a visited node

        We each the end if either the priority queue is empty or if we have reached the target node

        Intuition behind this algorithm, at every step we take the next best path to traverse
        So when we have reached the end node, it would be through the best path, so we can end there

        And at the end return the value from the array

        """

        # we have the edges of an undirected graph with it's probabilities
        # let's form the undirected graph we will need this to get access to neighbors
        # each neighbor comes with a probability

        """
        edges: List[List[int]], 
        succProb: List[float]
        """

        undirectedGraph = {

        }

        for index, edge in enumerate(edges):

            edgeProbability = succProb[index] # float
            nodeA = edge[0]
            nodeB = edge[1]

            if nodeA not in undirectedGraph:
                undirectedGraph[nodeA] = []
            
            undirectedGraph[nodeA].append((edgeProbability, nodeB))
            
            if nodeB not in undirectedGraph:
                undirectedGraph[nodeB] = []

            undirectedGraph[nodeB].append((edgeProbability, nodeA))

        maxProbToReachNode = [0 for _ in range(n)]

        maxProbToReachNode[start_node] = 1

        # we need to find maxProbToReachNode[end]

        maxHeapPQ = []

        # let's add the start node to this queue
        heappush(maxHeapPQ, (-1, start_node))

        visitedNodes = set() 

        while len(maxHeapPQ) > 0 and len(visitedNodes) < n:

            # here is where we implement dijkstras algorithm
            # Get the next best node to process
            prob, nodeNumber = heappop(maxHeapPQ) # (-Prob, nodeNumber)

            if nodeNumber == end_node:
                break

            visitedNodes.add(nodeNumber)

            prob = (-1) * prob
            # Get all the neighbors of this node
            if nodeNumber in undirectedGraph:
                for edgeProbability, neighbor in undirectedGraph[nodeNumber]:

                    # check if we need to update the probability
                    neighborBestProbability = maxProbToReachNode[neighbor]

                    # new probability =
                    newProb = maxProbToReachNode[nodeNumber] * edgeProbability

                    if newProb > neighborBestProbability:
                        maxProbToReachNode[neighbor] = newProb

                    # add this to priorityqueue if not yet visited
                    if neighbor not in visitedNodes:
                        heappush(maxHeapPQ, ((-1) * maxProbToReachNode[neighbor], neighbor))
            
        return maxProbToReachNode[end_node]
29400