You are given an undirected weighted graph of n
nodes (0-indexed), represented by an edge list where edges[i] = [a, b]
is an undirected edge connecting the nodes a
and b
with a probability of success of traversing that edge succProb[i]
.
Given two nodes start
and end
, find the path with the maximum probability of success to go from start
to end
and return its success probability.
If there is no path from start
to end
, return 0. Your answer will be accepted if it differs from the correct answer by at most 1e-5.
Example 1:
Input: n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.2], start = 0, end = 2 Output: 0.25000 Explanation: There are two paths from start to end, one having a probability of success = 0.2 and the other has 0.5 * 0.5 = 0.25.
Example 2:
Input: n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.3], start = 0, end = 2 Output: 0.30000
Example 3:
Input: n = 3, edges = [[0,1]], succProb = [0.5], start = 0, end = 2 Output: 0.00000 Explanation: There is no path between 0 and 2.
Constraints:
2 <= n <= 10^4
0 <= start, end < n
start != end
0 <= a, b < n
a != b
0 <= succProb.length == edges.length <= 2*10^4
0 <= succProb[i] <= 1
- There is at most one edge between every two nodes.
Related Topics:
Graph
Direct application of Dijkstra algorithm except that usually the cost is the smaller the better, but in this problem the probability is the greater the better.
// OJ: https://leetcode.com/problems/path-with-maximum-probability/
// Author: github.com/lzl124631x
// Time: O(ElogE)
// Space: O(E)
class Solution {
public:
double maxProbability(int n, vector<vector<int>>& E, vector<double>& P, int start, int end) {
vector<vector<pair<int, double>>> G(n);
for (int i = 0; i < E.size(); ++i) {
int u = E[i][0], v = E[i][1];
G[u].emplace_back(v, P[i]);
G[v].emplace_back(u, P[i]);
}
priority_queue<pair<double, int>> pq;
pq.emplace(1, start);
vector<double> dist(n, 0);
dist[start] = 1;
while (pq.size()) {
auto [p, u] = pq.top();
pq.pop();
if (p < dist[u]) continue;
for (auto &[v, w] : G[u]) {
if (dist[v] >= dist[u] * w) continue;
dist[v] = dist[u] * w;
pq.emplace(dist[v], v);
}
}
return dist[end];
}
};
Or use multiset
// OJ: https://leetcode.com/problems/path-with-maximum-probability/
// Author: github.com/lzl124631x
// Time: O(ElogE)
// Space: O(E)
class Solution {
public:
double maxProbability(int n, vector<vector<int>>& edges, vector<double>& succProb, int start, int end) {
vector<vector<pair<int, double>>> G(n);
for (int i = 0; i < edges.size(); ++i) {
auto &e = edges[i];
G[e[0]].emplace_back(e[1], succProb[i]);
G[e[1]].emplace_back(e[0], succProb[i]);
}
multiset<pair<double, int>> s; // prob, index
unordered_map<int, double> m;
s.emplace(1, start);
while (s.size()) {
auto p = *s.rbegin();
s.erase(prev(s.end()));
int u = p.second;
if (m.count(u)) continue;
m[u] = p.first;
if (u == end) return m[u];
for (auto &[v, w] : G[u]) s.emplace(w * m[u], v);
}
return 0;
}
};