algorithm - 找到包含无向图中给定边的欧拉路径的最小成本（算法）

Question

如何在无向加权图中找到最小欧拉路径？（该路径必须包含给定的边）

边缘的权重是所有边缘的 2 个点的总和（例如：edge 4-9 weight=4+9=13）。

示例：有 6 个节点（N）和 5 条边（E）：

(1-5)
(6-1)
(5-5)
(2-4)
(2-4)

解决方案：我们必须向最小欧拉路径添加 2 条边：

1-2
1-2

在此示例中，第三个节点是孤立的，但这不是问题。目标：欧拉路径，包含所有起始边。在这个例子中，我们可以使用 2 个互补边 (1-2)(1-2) 来执行欧拉路径：5->5->1->2->4->2->1->6。所以我们访问了所有的起始边，互补边最少，我们只使用一次所有边。

什么是最好的算法来找到，什么时候1<N,E<100000，必须在 0.01 秒内运行？

标签： algorithmgraphundirected-grapheuler-path