Path with maximum probability
November 20, 2022
graphProblem URL: Path with maximum probability
We can use Dijkstra's algorithm to find the shortest path from the start node to the end node. We will keep track of the probability of the shortest path from the start node to the current node. Then we will iterate over each node until the end node, and we will check if the probability of the shortest path from the start node to the current node is greater than the probability of the shortest path from the start node to the previous node plus the probability of the edge from the previous node to the current node. If yes, we will update the probability of the shortest path from the start node to the current node. We will continue this process until we reach the end node.
class Solution:
def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start: int, end: int) -> float:
graph = collections.defaultdict(list)
for (u, v), w in zip(edges, succProb):
graph[u].append((v, w))
graph[v].append((u, w))
visited = set()
heap = [(-1, start)]
while heap:
prob, node = heapq.heappop(heap)
if node == end:
return -prob
visited.add(node)
for next_node, add_prob in graph[node]:
if next_node in visited:
continue
next_prob = prob * add_prob
heapq.heappush(heap, (next_prob, next_node))
return 0
Time complexity: O(nlog(n))
Space complexity: O(n)