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 java.util.*;
2
3public class Solution {
4 public double maxProbability(int n, int[][] edges, double[] succProb, int start, int end) {
5 List<List<Pair>> graph = new ArrayList<>();
6 for (int i = 0; i < n; i++) {
7 graph.add(new ArrayList<>());
8 }
9 for (int i = 0; i < edges.length; i++) {
10 int u = edges[i][0];
11 int v = edges[i][1];
12 double prob = succProb[i];
13 graph.get(u).add(new Pair(v, prob));
14 graph.get(v).add(new Pair(u, prob));
15 }
16
17 double[] maxProb = new double[n];
18 maxProb[start] = 1.0;
19 PriorityQueue<Pair> pq = new PriorityQueue<>((a, b) -> Double.compare(b.prob, a.prob));
20 pq.add(new Pair(start, 1.0));
21
22 while (!pq.isEmpty()) {
23 Pair curr = pq.poll();
24 int node = curr.node;
25 double prob = curr.prob;
26
27 if (node == end) {
28 return prob;
29 }
30
31 for (Pair neighbor : graph.get(node)) {
32 int nextNode = neighbor.node;
33 double edgeProb = neighbor.prob;
34 if (maxProb[nextNode] < prob * edgeProb) {
35 maxProb[nextNode] = prob * edgeProb;
36 pq.add(new Pair(nextNode, maxProb[nextNode]));
37 }
38 }
39 }
40
41 return 0.0;
42 }
43
44 private static class Pair {
45 int node;
46 double prob;
47
48 Pair(int node, double prob) {
49 this.node = node;
50 this.prob = prob;
51 }
52 }
53}The Java implementation follows a similar logic to the Python version, using a priority queue to determine the order of node processing based on probability. The graph is built using adjacency lists with auxiliary pairs defined to manage nodes and their associated current probability. By processing through the priority queue and updating paths with higher probabilities, this approach ensures that the maximum probability path is effectively identified. The use of double to compare and store probabilities is crucial due to the precision required in such computations.
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.
This Python solution adapts the Bellman-Ford algorithm by carrying out edge relaxation iteratively, updating the path if a higher probability (converted to a lower negative log value) is discovered. It calculates the log-probability instead of direct product and converts back the resultant path strength using exponentiation. The algorithm stops early if no updates are performed in an iteration, indicating convergence to optimal.