本文涉及知识点
C++图论
LeetCode1514. 概率最大的路径
给你一个由 n 个节点(下标从 0 开始)组成的无向加权图,该图由一个描述边的列表组成,其中 edges[i] = [a, b] 表示连接节点 a 和 b 的一条无向边,且该边遍历成功的概率为 succProb[i] 。
指定两个节点分别作为起点 start 和终点 end ,请你找出从起点到终点成功概率最大的路径,并返回其成功概率。
如果不存在从 start 到 end 的路径,请 返回 0 。只要答案与标准答案的误差不超过 1e-5 ,就会被视作正确答案。
示例 1:
输入:n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.2], start = 0, end = 2
输出:0.25000
解释:从起点到终点有两条路径,其中一条的成功概率为 0.2 ,而另一条为 0.5 * 0.5 = 0.25
示例 2:
输入:n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.3], start = 0, end = 2
输出:0.30000
示例 3:
输入:n = 3, edges = [[0,1]], succProb = [0.5], start = 0, end = 2
输出:0.00000
解释:节点 0 和 节点 2 之间不存在路径
提示:
2 <= n <= 104
0 <= start, end < n
start != end
0 <= a, b < n
a != b
0 <= succProb.length == edges.length <= 2*104
0 <= succProb[i] <= 1
每两个节点之间最多有一条边
和迪氏优化最短路的思想一样
源点集s:记录所有已经求出最短路的点。
mid:源点集任何一点s1出发的边。记录此边的终点t1,和 s t a r t → s 1 → t 1 start \rightarrow s1 \rightarrow t1 start→s1→t1的最大距离d。
目标点集t:记录所有没有求出最短路的点。
性质一:任意t中的点到start的距离 <= 任意s中的点到s的距离。
初始状态s只有start,start距离start是1.0。其它点只会小于等于1.0。
令s中有m个点,则距离start第m+1大的点,一定是mid的最大点。
用反证法证明:
s t a r t → s 1 → t 1 ⋯ t 2 start \rightarrow s1 \rightarrow t1 \cdots t2 start→s1→t1⋯t2 t1到start的距离一定大于等于t2的距离。即t1一定不劣于t2。
代码
核心代码
class Solution {
public:
double maxProbability(int n, vector<vector<int>>& edges, vector<double>& succProb, int start_node, int end_node) {
vector<vector<pair<int,double>>> neiBo(n);
for (int i = 0; i < edges.size(); i++) {
neiBo[edges[i][0]].emplace_back(edges[i][1],succProb[i]);
neiBo[edges[i][1]].emplace_back(edges[i][0], succProb[i]);
}
vector<double> dis(n, -2);
priority_queue<pair<double, int>> heap;
auto Add = [&](int cur, double dDis) {
if (dis[cur] > -1) { return; }
dis[cur] = dDis;
for (const auto& [next, d] : neiBo[cur]) {
heap.emplace(d * dDis, next);
}
};
Add(start_node, 1);
while (heap.size()) {
const auto [iDis, cur] = heap.top();
heap.pop();
Add(cur, iDis);
}
return max(0.0, dis[end_node]);
}
};
单元测试
int n;
vector<vector<int>> edges;
vector<double> succProb;
int start, end;
TEST_METHOD(TestMethod11)
{
n = 3, edges = { {0,1},{1,2},{0,2} }, succProb = { 0.5,0.5,0.2 }, start = 0, end = 2;
auto res = Solution().maxProbability(n, edges, succProb, start, end);
AssertEx(0.25, res);
}
TEST_METHOD(TestMethod12)
{
n = 3, edges = { {0,1},{1,2},{0,2} }, succProb = { 0.5,0.5,0.3 }, start = 0, end = 2;
auto res = Solution().maxProbability(n, edges, succProb, start, end);
AssertEx(0.3, res);
}
TEST_METHOD(TestMethod13)
{
n = 3, edges = { {0,1} }, succProb = { 0.5 }, start = 0, end = 2;
auto res = Solution().maxProbability(n, edges, succProb, start, end);
AssertEx(0.0, res);
}
TEST_METHOD(TestMethod14)
{
n = 3, edges = { {0,1}}, succProb = { 0.5}, start = 0, end = 2;
auto res = Solution().maxProbability(n, edges, succProb, start, end);
AssertEx(0.0, res);
}