algorithm - 找到通过顶点 u 和 v 的最小权重电路

Question

我有一个无向且连接（不完整）的顶点图，其中u和v可以是任何 2 个不同的顶点。我想构建从顶点u开始，通过v，然后返回u而不重复任何边的最小权重电路。这可以通过执行以下操作来完成吗？

1. 找到从u到v的最短路径- 称之为p1

2. 从图中删除p1的所有组成边

3. 找到从v到u的新最短路径- 称之为p2

4. 将所有已删除的边返回到图中，并将p1和p2连接在一起 - 称之为c1

考虑到通过u和v的约束， c1是可以构造的最小权重电路吗？如果是，我如何证明它，如果不是，为什么不呢？

这对我来说似乎很有意义，因为c1中包含的所有路径本身也是最短路径，但是我无法完全摆脱我可能会遗漏某些东西的感觉。

编辑：我已将“完全连接图”更改为“连接图”。“完全”暗示图表是完整的，这不是我的意思。

标签： algorithmgraph-theorygraph-algorithm

Answer 1

这是一个反例：

在完整图的情况下，假设图中未显示的所有边都具有较大的权重（例如 1000）。

p1会找到最短路径并将其1 - 1 - 1排除，禁止3 - 1+的实际答案1 - 3。

---

正如Falk Hüffner所建议的，这个任务可以通过边缘不相交最短对算法来解决。