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.
1using System;
2using System.Collections.Generic;
3
4public class Solution {
5 public double MaxProbability(int n, int[][] edges, double[] succProb, int start, int end) {
6 List<List<Tuple<int, double>>> graph = new List<List<Tuple<int, double>>>();
7 for (int i = 0; i < n; i++) {
8 graph.Add(new List<Tuple<int, double>>());
9 }
10 for (int i = 0; i < edges.Length; i++) {
11 int u = edges[i][0], v = edges[i][1];
12 double prob = succProb[i];
13 graph[u].Add(Tuple.Create(v, prob));
14 graph[v].Add(Tuple.Create(u, prob));
15 }
16
17 double[] maxProb = new double[n];
18 maxProb[start] = 1.0;
19
20 PriorityQueue<Tuple<double, int>, double> pq = new();
21 pq.Enqueue(Tuple.Create(1.0, start), -1.0);
22
23 while (pq.Count > 0) {
24 var (currProb, node) = pq.Dequeue();
25 currProb *= -1;
26
27 if (node == end) return currProb;
28
29 foreach (var (nextNode, edgeProb) in graph[node]) {
30 if (maxProb[nextNode] < currProb * edgeProb) {
31 maxProb[nextNode] = currProb * edgeProb;
32 pq.Enqueue(Tuple.Create(maxProb[nextNode], nextNode), -maxProb[nextNode]);
33 }
34 }
35 }
36
37 return 0.0;
38 }
39}The C# implementation uses a priority queue from .NET's collections to handle the nodes based on their probabilities, prioritizing nodes with the high probability of being part of the maximum product path. This logic requires the transformation of probability to a negative value before enqueuing to simulate handling of a max-heap. This implementation borrows principles from graph theory specifically related to weighted path calculations but adjusted for probabilities instead of traditional distance metrics.
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.
#include <cmath>
#include <limits>
using namespace std;
class Solution {
public:
double maxProbability(int n, vector<vector<int>>& edges, vector<double>& succProb, int start, int end) {
vector<double> logProb(n, -numeric_limits<double>::infinity());
logProb[start] = 0;
for (int i = 0; i < n - 1; ++i) {
bool updated = false;
for (int j = 0; j < edges.size(); ++j) {
int u = edges[j][0], v = edges[j][1];
double logProbVal = log(succProb[j]);
if (logProb[u] != -numeric_limits<double>::infinity() && logProb[u] + logProbVal > logProb[v]) {
logProb[v] = logProb[u] + logProbVal;
updated = true;
}
if (logProb[v] != -numeric_limits<double>::infinity() && logProb[v] + logProbVal > logProb[u]) {
logProb[u] = logProb[v] + logProbVal;
updated = true;
}
}
if (!updated) break;
}
return logProb[end] != -numeric_limits<double>::infinity() ? exp(logProb[end]) : 0.0;
}
};This C++ implementation involves a careful handling of numerical limits and logarithms. It executes in typical Bellman-Ford style across all edges, allowing for detection and maximization of paths using logarithmic transformations on probabilities. Looping for V-1 times enables comprehensive coverage of potential paths for the initial input conditions, with early termination ensured upon stagnation through exploitation of the updated state flag.