好吧，我现在手头的一项小工作遇到了问题……
主要目标是，有一个给定的图（没有权重和有向图），我必须发现总长度最小的一组路径（如果可能，只有一条路径，但它们可以更多），覆盖所有边。其他“约束”是图形是 DFA，因此路径应该以初始状态开始，并以接受状态结束（它们被标记）。
最初我发现这和中国邮递员问题很像，事实上也确实如此。但在我的情况下，图形是有向的（我相信这会改变一些事情），并且不止一次处理边没有任何问题，因为结果路径仍然是最短的。
我读过一些关于欧拉路径和 T-Joins 的东西，这可能是我的问题的解决方案。如果我理解正确，我应该做的是在我的图中找到一条欧拉路径，如果没有，让它存在，复制 T-Joins，或者类似的东西......我遇到了很多麻烦理解这一点，我什至不知道这是否是我问题的答案......（我在这里找到的最短和最容易理解的文本：http ://en.wikipedia.org/wiki/Route_inspection_problem ）
仅举一个简短的例子，给定这张图（1 是初始值，5 是接受度）：
1 -> 2;
2 -> 3;
2 -> 4;
4 -> 5;
我的问题的答案应该是：1 -> 2 -> 4 -> 5 和 1 -> 2 -> 3。（在这种情况下，我还必须处理 3 不是接受状态的事实，但是边缘必须被覆盖。但我可以通过将所有没有边缘的状态标记为其他节点作为接受状态来轻松解决这个问题）。
希望我解释得很好。
提前致谢！