LeetCode 1514: Path with Maximum Probability
Problem Description
Explanation
To solve this problem, we can use Dijkstra's algorithm to find the path with the maximum probability of success from the start node to the end node. We will keep track of the success probabilities for each node in the graph and update them as we explore different paths.
- Create an adjacency list representation of the graph using the given edge list and success probabilities.
- Initialize an array to store the success probability for each node, with the probability of the start node being 1.0 and all other nodes having a probability of 0.0.
- Use a priority queue to explore nodes based on their success probabilities.
- Start from the start node and explore neighboring nodes, updating their success probabilities with the maximum probability from the current node.
- Continue exploring nodes until reaching the end node or until the priority queue is empty.
- Return the success probability of the end node.
Time complexity: O(E log V), where E is the number of edges and V is the number of nodes. Space complexity: O(V) for storing the success probabilities and the priority queue.
Solutions
import java.util.*;
class Solution {
public double maxProbability(int n, int[][] edges, double[] succProb, int start, int end) {
Map<Integer, List<double[]>> graph = new HashMap<>();
for (int i = 0; i < edges.length; i++) {
int[] edge = edges[i];
graph.computeIfAbsent(edge[0], k -> new ArrayList<>()).add(new double[]{edge[1], succProb[i]});
graph.computeIfAbsent(edge[1], k -> new ArrayList<>()).add(new double[]{edge[0], succProb[i]});
}
double[] prob = new double[n];
prob[start] = 1.0;
PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> Double.compare(prob[b], prob[a]));
pq.offer(start);
while (!pq.isEmpty()) {
int node = pq.poll();
if (node == end) {
return prob[node];
}
if (!graph.containsKey(node)) {
continue;
}
for (double[] next : graph.get(node)) {
int neighbor = (int) next[0];
double successProb = next[1];
if (prob[node] * successProb > prob[neighbor]) {
prob[neighbor] = prob[node] * successProb;
pq.offer(neighbor);
}
}
}
return 0.0;
}
}Loading editor...