时间戳

首页 > 解决方案 > 找到最可靠的路径 - Dijkstra 算法

algorithm - 找到最可靠的路径 - Dijkstra 算法

问题描述

给定一个有向图 G = (V, E)，其中每条边 (u, v) ∈ E 都有一个关联值 r(u, v)，它是 0 ≤ r(u, v) 范围内的实数) ≤ 1，表示从顶点 u 到顶点 v 的通信通道的可靠性。我们将 r(u, v) 解释为从 u 到顶点的通道不会失败的概率，并且我们假设这些概率是独立的。给出一个有效的算法来找到两个给定顶点之间最可靠的路径。

     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

有人可以以最简单的方式解释最可靠的路径吗？

这个问题来自Introduction to Algorithms, 3rd edition, chp 24.3

提前致谢！

标签： algorithmdata-structuresgraphcomputer-sciencedijkstra

解决方案

我们将 r(u, v) 解释为从 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))边缘的长度。

推荐阅读