2

给定一个无向图 G = (V, E)，G 中的边具有非负权重。

[1] 如何找到两个节点 s 和 t 之间的所有边不相交和等成本路径？

[2] 如何找到两个节点 s 和 t 之间的所有边不相交路径？

[3] 如何找到两个节点 s 和 t 之间的所有顶点不相交和等成本路径？

[4] 如何找到两个节点 s 和 t 之间的所有顶点不相交路径？

任何近似算法代替？

4

1 回答 1

4

构建一棵树，其中每个节点都表示通过单向图的路径。

我知道，树也是图，但在这个答案中，我将使用以下具有此含义的术语：

  • 顶点：是单向图中的顶点。它不是我树中的一个节点。
  • edge：是单向图中的一条边。它不是我树的一部分。
  • 节点：我的树中的一个顶点，而不是你的图中的一个顶点。
  • root：我树上唯一没有父节点的节点。
  • 叶：我的树中没有子节点的任何节点。

我不会谈论我的树中的边缘，所以没有关于树边缘的词。此答案中的每条边都是您图表的一部分。

构建树的算法

树的根是仅包含顶点 s 且不包含边的路径的表示。让它的权重为0。

对该树中的每个节点执行以下操作：

取该节点表示的路径的末端顶点（我称其为实际节点）并找到所有远离该末端顶点的边。
如果：没有从这个顶点引出的边，你走到了死胡同。这条路径永远不会通向顶点 t。所以将此节点标记为叶子并赋予它无限权重。
别的：

对于这些边中的每一个：
将子节点添加到实际节点。让它成为实际节点的副本。将边缘附加到路径的末端，然后将边缘末端顶点也附加到路径。（所以每条路径都遵循模式 vertex-edge-vertex-edge-vertex-...）
现在在树中向上遍历，回到根并检查是否有任何前辈具有与刚才相同的结束顶点添加了结束顶点。
如果您有匹配项，则新生成的节点是包含循环的路径的表示。将此节点标记为叶子并赋予其无限权重。
否则如果没有循环，只需将新添加的边权重添加到节点权重中即可。现在测试，如果新生成的节点的结束顶点是顶点 t。
如果确实是，将此节点标记为叶子，因为此节点表示的路径是从 s 到 t 的有效路径。

该算法总是在有限时间内结束。最后，你的树上有 3 种类型的叶子：

  • 代表具有无限权重的死胡同的节点
  • 代表循环的节点，也具有无限权重
  • 表示从 s 到 t 的有效路径的节点，其权重是作为该路径一部分的所有边权重的总和。

由叶子表示的每条路径都有其单独的边序列（但可能包含相同的顶点序列），因此具有有限权重的叶子表示从 s 到 t 的完整边不相交路径集。这就是练习[2]的解法。

现在对所有具有有限权重的叶子执行以下操作：
将其权重及其路径写入列表。按权重对列表进行排序。现在具有相同权重的路径是列表中的邻居，您可以在此排序列表中找到并提取所有等价路径组。这就是练习[1]的解法。

现在，对该列表中的每个条目执行以下操作：
将其顶点列表添加到该列表中的每个路径。完成此操作后，您将拥有一个包含以下列的表：

  • 重量
  • 小路
  • 第一个顶点（总是 s）
  • 第二个顶点
  • 第三个顶点
  • ...

按顶点排序此表字典序，然后按权重排序所有顶点（按第 1 个顶点、第 2 个顶点、第 3 个顶点、...、权重排序）如果此排序表中的一行与前一行具有相同的顶点序列，然后删除这一行。

这是两个节点 s 和 t 之间所有顶点不相交路径的列表，因此它是练习 [4] 的解决方案。

在此列表中，您可以找到所有等成本路径作为邻居，因此您可以轻松地从该列表中提取两个节点 s 和 t 之间的所有顶点不相交和等成本路径组，所以这里有练习 [3 ] .

于 2012-07-24T10:31:43.143 回答