寻找通过顶点 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中包含的所有路径本身也是最短路径，但是我无法完全摆脱我可能会错过某些东西的感觉。

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

Answer 1

这是一个反例：

\n\n

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

\n

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

\n\n

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

\n