寻找通过顶点 u 和 v 的最小权重电路
Finding the minimum weight circuit that passes through vertices u and v
我有一个无向且连通（不完整）的顶点图，其中 u 和 v 可以是任意两个不同的顶点。我想构建从顶点u开始，通过v[=的最小权重电路61=]，然后returns回到u，不重复任何边。可以通过执行以下操作来完成吗？
求从u到v[=的最短路径61=] - 称之为 p1
从图中删除 p1 的所有组成边
寻找从v到u[的新的最短路径 - 称之为 p2
将所有删除的边返回到图中，并将 p1 和 p2 连接在一起 - 调用此 c1
是c1可以构造的最小权重电路，考虑到通过u[的约束=62=]和v？如果是，我如何证明，如果不是，为什么不？
这对我来说似乎很有意义，因为 c1 中包含的所有路径本身也是最短路径，但是我无法完全摆脱我可能会丢失的感觉东西。
编辑：我已将“完全连接图”更改为“连接图”。 "fully" 暗示图表是完整的，这不是我的意思。
这是一个反例：
在完整图的情况下，假设图中未显示的所有边都具有较大的权重（如 1000）。
p1 会找到最短路径 1 - 1 - 1 并排除它，禁止 3 - 1 + 1 - 3.
的实际答案
根据 , this task can be solved by Edge disjoint shortest pair algorithm 的建议。
如果我没理解错的话，这相当于找到从 u 到 v 的两条边不相交的路径，同时最小化它们的总权重。这是 Minimum Cost Flow with a flow of two, so it can be solved in polynomial time and is likely not NP-hard. Suurballe's algorithm solves it for directed graphs, and it should be possible to adapt it to undirected graphs (it seems that this Wikipedia page 试图这样做的特例。
我有一个无向且连通（不完整）的顶点图，其中 u 和 v 可以是任意两个不同的顶点。我想构建从顶点u开始，通过v[=的最小权重电路61=]，然后returns回到u，不重复任何边。可以通过执行以下操作来完成吗？
求从u到v[=的最短路径61=] - 称之为 p1
从图中删除 p1 的所有组成边
寻找从v到u[的新的最短路径 - 称之为 p2
将所有删除的边返回到图中，并将 p1 和 p2 连接在一起 - 调用此 c1
是c1可以构造的最小权重电路，考虑到通过u[的约束=62=]和v？如果是，我如何证明，如果不是，为什么不？
这对我来说似乎很有意义，因为 c1 中包含的所有路径本身也是最短路径，但是我无法完全摆脱我可能会丢失的感觉东西。
编辑：我已将“完全连接图”更改为“连接图”。 "fully" 暗示图表是完整的，这不是我的意思。
这是一个反例：
在完整图的情况下，假设图中未显示的所有边都具有较大的权重（如 1000）。
p1 会找到最短路径 1 - 1 - 1 并排除它，禁止 3 - 1 + 1 - 3.
根据
如果我没理解错的话，这相当于找到从 u 到 v 的两条边不相交的路径，同时最小化它们的总权重。这是 Minimum Cost Flow with a flow of two, so it can be solved in polynomial time and is likely not NP-hard. Suurballe's algorithm solves it for directed graphs, and it should be possible to adapt it to undirected graphs (it seems that this Wikipedia page 试图这样做的特例。