c# - 试图找到在图中导航一组边的最快方法

Question

我不确定我应该使用哪种算法来完成这项任务。我有一个节点图。一些节点与需要遍历的加权线相连。然而，每个节点都与一条加权的双向线相连。只有部分线路必须经过，而其他线路仅用于导航。我需要找到一条路径来遍历所有这些必需的线(双向)，但只能遍历一次。我知道我必须从哪个节点开始。

现实世界的问题是我有一个需要从 CNC 图案中切割的边缘列表。我正在尝试减少 CNC 机器花费在切割这种模式上的时间。我知道我总是想从原点开始，但我不在乎图案在哪里结束，只要将图案中的所有小块都剪掉即可。我知道切出零件的每个边缘需要多长时间，而且机器足够准确，可以抬起头部并从该位置开始到任何点。我的图并不大，一般情况下可能多达 100 个节点。

这与旅行推销员不同，因为我不必在同一个地方开始和结束，而且我可以(并且必须)多次点击一个节点。

Djikstras 算法不起作用，因为我需要遍历所有节点才能切割所有边......我不只是想找到从 A 点到 B 点的最快方法。

奖励，我需要在 C# 中实现它，但即使我只知道什么算法，我也可以对其进行编程。

这是我需要剪下的图案的示例图片。注意，有一条对角线和一条弧线我忘记分配权重，对角线可以是 50，弧线可以是 75:

Answer 1

我相信这可以作为路由检查问题的一个案例来解决。

https://en.wikipedia.org/wiki/Route_inspection_problem

您需要确保该图存在欧拉回路，这可以通过运气或通过将奇数顶点连接在一起来实现。