在建模网络的图形上的Dijkstra算法

Question

我们有G = (V, E)一个comm的有向图.每个边缘具有不失败概率r(u, v)(定义为边缘权重)的网络,其位于区间[0,1]中.概率是独立的,因此从一个顶点到另一个顶点,如果我们乘以所有概率,我们得到整个路径没有失败的概率.

我需要一个有效的算法来找到其他给定的顶点,从一个给定的顶点最可靠的路径(即从第一个顶点到第二路径,该路径是最可能失败).我知道这log(r · s) = log r + log s会有所帮助.

这是我到目前为止 - :

DIJKSTRA-VARIANT (G, s, t)
for v in V:
    val[v] ? ?
A ? ?
Q ? V to initialize Q with vertices in V.
val[s] ? 0
while Q is not ? and t is not in A
    do x ? EXTRACT-MIN (Q)
    A ? A ? {x}
    for each vertex y ? Adj[x]
        do if val[x] + p(x, y) < val[y]:
           val[y] = val[x] + p(x, y)

s是源顶点并且t是目标顶点.当然,我没有利用该log属性,因为我无法理解如何使用它.底部算法的松弛部分需要修改,val阵列将捕获结果.没有日志,它可能会存储次高概率.我该如何修改要使用的算法log？

Answer 1

现在，你的代码有

do if val[x] + p(x, y) < val[y]:
    val[y] = val[x] + p(x, y)

由于本例中的边权重代表概率，因此您需要将它们相乘（而不是相加）：

do if val[x] * p(x, y) > val[y]:
    val[y] = val[x] * p(x, y)

我已将符号更改为>，因为您希望概率尽可能大。

对数很有用，因为 (1) log(xy) = log(x) + log(y)（如您所说）和总和比乘积更容易计算，并且 (2)log(x)是 的单调函数x，因此log(x)和x的最大值位于同一位置。因此，您可以处理概率的对数，而不是概率本身：

do if log_val[x] + log(p(x, y)) > log_val[y]:
    log_val[y] = log_val[x] + log(p(x, y))

编辑添加（因为我没有足够的代表来发表评论）：您需要将val数组初始化为0，而不是Infinity，因为您正在计算最大值而不是最小值。（因为您想要最大的不失败概率。）因此，在对数转换之后，初始log_val数组值应该是-Infinity。