-[685. Redundant Connection II](en/1-1000/685-redundant-connection-ii.md) was solved in_Python_.

-[1584. Min Cost to Connect All Points](en/1001-2000/1584-min-cost-to-connect-all-points.md) was solved in_Python, Java, C++, JavaScript, C#, Go, Ruby_ and 2 ways.

-[207. Course Schedule](en/1-1000/207-course-schedule.md) was solved in_Python, Java, C++, C#_ and 2 ways.

-[1514. Path with Maximum Probability](en/1001-2000/1514-path-with-maximum-probability.md) was solved in_Python_ and 2 ways.

More LeetCode problems will be added soon...

LeetCode link:[1514. Path with Maximum Probability](https://leetcode.com/problems/path-with-maximum-probability), difficulty:**Medium**.

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**.

**Input**:`n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.2], start = 0, end = 2`

**Output**:`0.25000`

**Explanation**:`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.`

**Input**:`n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.3], start = 0, end = 2`

**Output**:`0.30000`

**Input**:`n = 3, edges = [[0,1]], succProb = [0.5], start = 0, end = 2`

**Output**:`0.00000`

**Explanation**:`There is no path between 0 and 2.`

- There is at most one edge between every two nodes.

<details>

<summary>Hint 1</summary>

Multiplying probabilities will result in precision errors.

</details>

<details>

<summary>Hint 2</summary>

Take log probabilities to sum up numbers instead of multiplying them.

</details>

<details>

<summary>Hint 3</summary>

Use Dijkstra's algorithm to find the minimum path between the two nodes after negating all costs.

</details>

We can use**Dijkstra's algorithm**.

This animation is about**Dijkstra's algorithm** to find the shortest path between`a` and`b`.

It picks the unvisited vertex with the lowest distance, calculates the distance through it to each unvisited neighbor, and updates the neighbor's distance if smaller. Mark**visited** (set to red) when done with neighbors.

In short,**Dijkstra's algorithm** means**to find the nearest point and walk through it, and never go back. Repeatedly**.

**V**: vertex count,**E**: Edge count.

* Time:`O(V * V)`.

* Space:`O(V + E)`.

* Time:`O(E * log(E))`.

* Space:`O(V + E)`.

The code will time out when executed on LeetCode, but this is not a problem with the code itself. The`heap sort` implementation below will not time out.

classSolution:

defmaxProbability(self,n:int,edges: List[List[int]],succ_prob: List[float],start_node:int,end_node:int) ->float:

node_to_pairs= defaultdict(set)

for i, (source_node, target_node)inenumerate(edges):

node_to_pairs[source_node].add((target_node, succ_prob[i]))

node_to_pairs[target_node].add((source_node, succ_prob[i]))

max_probabilities= [0]* n

max_probabilities[start_node]=1

visited= [False]* n

for _inrange(n-1):

current_node=None

maximum_probability=0

for node, probabilityinenumerate(max_probabilities):

ifnot visited[node]and probability> maximum_probability:

maximum_probability= probability

current_node= node

if current_nodeisNone:

visited[current_node]=True

for target_node, probabilityin node_to_pairs[current_node]:

probability_= probability* max_probabilities[current_node]

if probability_> max_probabilities[target_node]:

max_probabilities[target_node]= probability_

return max_probabilities[end_node]

import heapq

classSolution:

defmaxProbability(self,n:int,edges: List[List[int]],succ_prob: List[float],start_node:int,end_node:int) ->float:

node_to_pairs= defaultdict(set)

for i, (source_node, target_node)inenumerate(edges):

node_to_pairs[source_node].add((target_node, succ_prob[i]))

node_to_pairs[target_node].add((source_node, succ_prob[i]))

max_probabilities= [0for nodeinrange(n)]

max_probabilities[start_node]=1

items= [(-1, start_node)]

while items:

current_probability, current_node= heapq.heappop(items)

if current_node== end_node:

return-current_probability

for target_node, probabilityin node_to_pairs[current_node]:

probability_=abs(current_probability)* probability

if probability_> max_probabilities[target_node]:

max_probabilities[target_node]= probability_

heapq.heappush(items, (-probability_, target_node))

import heapq

classSolution:

defmaxProbability(self,n:int,edges: List[List[int]],succ_prob: List[float],start_node:int,end_node:int) ->float:

node_to_pairs= defaultdict(set)

for i, (source_node, target_node)inenumerate(edges):

node_to_pairs[source_node].add((target_node, succ_prob[i]))

node_to_pairs[target_node].add((source_node, succ_prob[i]))

max_probabilities= [0for nodeinrange(n)]

max_probabilities[start_node]=1

items= [(-1, start_node)]

visited= [False]* n# added 1

while items:

current_probability, current_node= heapq.heappop(items)

if current_node== end_node:

return-current_probability

if visited[current_node]:# added 3

visited[current_node]=True# added 2

for target_node, probabilityin node_to_pairs[current_node]:

if visited[target_node]:# added 4

probability_=abs(current_probability)* probability

if probability_> max_probabilities[target_node]:

max_probabilities[target_node]= probability_

heapq.heappush(items, (-probability_, target_node))