找到最可靠的路径-Dijkstra算法
给出了一个有向图G= ( v，E)，其中每个边(u，v)∈E有一个相关联的值r(u，v)，它是0≤r(u，v)≤1范围内的实数，表示从顶点u到顶点v的通信通道的可靠性，我们将r(u，v)解释为从u到u的通道不会失败的概率，我们假设这些概率是独立的。给出了在两个给定顶点之间寻找最可靠路径的有效算法。
a
/ \
b<--c a directed to c; c directed to b; b directed to a 假设这是图G= (V，E)；顶点a是根，其中一个边是a to c，a=u&c=v，所以边是(u，v)。我想用Dijkstra的算法来解决这个问题，但不确定如何解决。
a
\
b<--c path c: a -> c & b: a -> c -> b有人能用最简单的方法解释最可靠的路径吗？
这个问题来自于算法导论，第三版，chp 24.3
提前感谢！
回答 1
Stack Overflow用户
发布于 2020-11-24 09:52:24
我们将r(u，v)解释为从u到u的通道不会失败的概率，并假定这些概率是独立的。
由此可以推断，给定路径不会失败的概率等于构成该路径的所有边的r(u,v)的(u,v)的乘积。
你想要最大限度地利用这个产品。
这就像最短路径问题，对于这个问题，你肯定知道一个算法，除了最小化一个和，你在试图最大化一个乘积。
从积到和有一个很酷的工具:它是对数。对数是一个递增函数，因此最大化一个乘积就等于使该乘积的对数最大化。但对数具有额外的酷特性，即产品的对数等于对数之和：
log(a * b * c * d * ...) = log(a) + log(b) + log(c) + log(d) + ...因此，使可信赖性r(u,v)的乘积最大化与使日志可靠性log(r(u,v))之和最大化一样。
由于可靠性是边的概率，所以它们是0(排除)和1(包括)之间的值。可以排除0，因为如果边的可靠性为0，则可以从图中删除该边。因为0 < r(u,v) <= 1，所以log(r(u,v))是负值或0。
所以你试图最大化一个负值之和。这与最小化相反值的和完全相同。
因此:应用最短路径算法，使用-log(r(u,v))作为边的长度.
https://stackoverflow.com/questions/64991937
复制
相似问题
findOne mongoose查询未正常工作
分页不能正常工作的Mongoose查询
populate返回空查询mongoose
Mongoose查询返回空数组
Mongoose查询返回空数组
领取专属 10元无门槛券
AI混元助手 在线答疑
洞察 腾讯核心技术
剖析业界实践案例
腾讯云开发者
