0

我想知道，如果有一个加权图 G(V,E)，并且我需要在其中找到任意两个顶点 S 和 T 之间的一条最短路径，那么我可以使用 Dijkstras 算法。但是我不确定当我们需要找到从 S 到 T 的所有不同的最短路径时如何做到这一点。它是否可以在 O(n) 时间内解决？我还有一个问题，比如如果我们假设图中边的权重只能在某个范围内假设值，比如说 1 <=w(e)<=2 这会影响时间复杂度吗？

4

2 回答 2

0

(a) 使用来自 s 的 BFS 来标记像往常一样访问的节点，同时更改以下内容：

(b) 对于每个节点 v，它有一个记录 L(v) 表示 v 所在的层，记录 f(v) 表示传入路径的数量：

(c) 每次在另一个节点的 v2 邻居中找到节点 v1 时：

(d) 如果 v1 不在队列中，则将其添加到队列中，L(v1) = L(v2) + 1,f(v1)+ = f(v2)

(d) 如果 v1 已经在队列中并且 L(v1) 等于 L(v2)，则什么也不做。

(e) 如果 v1 已经在队列中，但 L(v1) 不等于 L(v2)，则 f(v1)+ = f(v2)

(f) 直到在这个修改后的 BFS 中，t 第一次从队列中弹出，我们有 f(t)

(g) 而这个 f(t) 表示从 s 到 t 的不同最短路径的数量

这可能会解决您的问题。

于 2014-09-20T19:05:26.483 回答
0

您可以使用 Dijkstra 来完成。在 Dijkstra 的算法中，您根据每个节点与源的距离为每个节点分配标签，并根据该距离（最小的优先）解决节点。一旦目标节点确定下来，您就拥有了最短路径的长度。要检索路径（=边缘序列），您可以跟踪您解决的每个节点的父节点。要检索所有可能的路径，您必须考虑每个节点的多个父节点。

一个小例子：

假设您有一个看起来像这样的图（为简单起见，所有边的权重为 1）：

       B
      / \
     A   C - D
      \ /
       E

当您执行 dijkstra 以找到距离 A->D 时，您将得到 3。您将首先以距离 0 解决节点 A，然后以距离 1 结算节点 B 和 E，以距离 2 结算节点 C，最后以距离 3 结算节点 D。要获得路径，您会在解决节点时记住它们的父节点。在这种情况下，您首先将 B 和 C 的父节点设置为节点 A。然后您需要将节点 C 的父节点设置为 B 和 E，因为它们都提供相同的长度。节点 D 将节点 C 作为父节点。

当您需要路径时，您可以只跟随父指针，从 D 开始，每次节点有多个父节点时分支。这将为您在节点 C 处提供一个分支。

上面评论中提到的帖子使用了相同的原理，虽然它不允许您实际提取路径，但它只给您计数。最后一点：Dijkstra 不是线性时间算法，因为您需要执行大量操作来维护队列和节点集。

于 2012-10-27T23:17:41.530 回答