Sponsored
Sponsored
The approach involves using Dijkstra's algorithm but instead of finding the shortest path, we need to find the path with the maximum product of probabilities. This can be achieved by using a max-heap (or priority queue) to always extend the path with the largest accumulated probability of success. The algorithm initializes a maximum probability set for each node starting from the start node with a probability of 1, then iteratively updates the probabilities by considering the edges connected to the current node, updating if a path with higher probability is found.
Time Complexity: O(E log V), where E is the number of edges and V is the number of vertices, due to the use of the priority queue.
Space Complexity: O(V + E), for storing the graph and additional data structures like the probability set and heap.
1import heapq
2
3class Solution:
4 def maxProbability(self, n, edges, succProb, start, end):
5 graph = [[] for _ in range(n)]
6 for (u, v), prob in zip(edges, succProb):
7 graph[u].append((v, prob))
8 graph[v].append((u, prob))
9
10 max_prob = [0.0] * n
11 max_prob[start] = 1.0
12
13 heap = [(-1.0, start)]
14
15 while heap:
16 curr_prob, node = heapq.heappop(heap)
17 curr_prob *= -1
18
19 if node == end:
20 return curr_prob
21
22 for neighbor, edge_prob in graph[node]:
23 if max_prob[neighbor] < curr_prob * edge_prob:
24 max_prob[neighbor] = curr_prob * edge_prob
25 heapq.heappush(heap, (-max_prob[neighbor], neighbor))
26
27 return 0.0The implementation uses a max-heap to prioritize nodes with a larger accumulated probability. The graph is represented using adjacency lists. Initially, the start node has an accumulated probability of 1.0, and we update the probabilities for its connected nodes through the priority queue. By always processing the node with the largest probability, and updating its neighbors accordingly, we ensure the most probable path is found. If the end node is reached, the current probability is returned; otherwise, 0.0 is returned indicating no path exists.
The Bellman-Ford algorithm traditionally calculates shortest paths in a weighted graph and can be adapted here to maximize a product instead. Given the properties of logarithms, maximizing the product of probabilities can be converted to minimizing the sum of the negative logarithm values, allowing direct use of Bellman-Ford's relaxation principle. This transformation reduces the problem of maximizing path probabilities to a more conventional structure that minimization algorithms handle well, iterating across all edges and vertices.
Time Complexity: O(V * E), where V is the number of vertices and E is the number of edges in the graph, each edge potentially causing updates across V-1 iterations.
Space Complexity: O(V), for storing probability values and log-converted results for paths during processing.
In Java, the solution leverages the Bellman-Ford algorithm's ability to handle weight computations by translating probabilities into logarithmic values, iterating across edges and vertices to relax paths and optimize probabilities. Results translated back using exponentiation confirm the largest product path and terminate early upon convergence detection via update flag, typical of Bellman-Ford methods.