给定一个有向图 G = (V, E)，其中每条边 (u, v) ∈ E 都有一个关联的 r(u, v) 值，是 0 ≤ r(u, v) ≤ 1 范围内的实数，表示从顶点 u 到顶点 v 的通信 channel 的可靠性。我们将 r(u, v) 解释为这 从 u 到 的 channel 不会失败的概率，我们假设这些概率 是独立的。给出一个有效的算法来找到两个给定之间最可靠的路径 顶点。
a
/ \
b<--c a directed to c; c directed to b; b directed to a
假设这是图 G = (V, E);顶点a是根，其中一条边是a到c。 a = u & c = v 所以边是 (u, v)。我想用 Dijkstra 算法来解决这个问题，但不知道如何解决。
a
\
b<--c path c: a -> c & b: a -> c -> b
有人可以用最简单的方式解释最可靠的路径吗？
此问题来自《算法导论》，第 3 版，第 24.3 章
提前致谢!
最佳答案
We interpret r(u, v) as the probability that the channel from u to will not fail, and we assume that these probabilities are independent.
由此您可以推断出给定路径不会失败的概率等于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))作为边缘的长度。
关于algorithm - 寻找最可靠的路径——Dijkstra算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/64991937/