有环有向图全边覆盖最短路径求解及与标准问题的同构性问询

你描述的是有向图中国邮递员问题（Directed Chinese Postman Problem, DCPP），目标是在有限、有向、强连通的图中找到遍历所有边至少一次的最短路径。

和无向图欧拉路径问题的关系 #

• 二者不存在同构关系。无向图欧拉路径是判定+构造类问题，要求找到恰好遍历所有边一次的路径，本身没有优化过程，且无向边没有方向约束，无法直接映射到有向图的约束条件中，其判定规则（图连通且奇度节点数为0或2）也不适用于有向场景。
• 仅在特殊场景下求解逻辑重合：当你的有向图满足「所有节点入度等于出度」时，DCPP的最优解就是该有向图的欧拉回路，此时可以用和无向欧拉路径同源的Hierholzer算法构造解。

和旅行商问题（TSP）的关系 #

• 二者不存在同构关系。两者核心目标完全不同：DCPP要求覆盖所有边，TSP要求找到恰好访问所有节点一次的最短回路。
• 二者复杂度类完全不同：有向强连通图的DCPP属于P类问题，可通过最小费用流算法在多项式时间内求解；而通用TSP属于NP难问题，不存在已知的多项式时间精确解法，不存在多项式时间下的双向映射空间。
• 仅存在有限的单向归约关系：部分TSP变种可以被归约为边覆盖类问题，但该归约不具备双向性，不属于同构范畴。

内容的提问来源于stack exchange，提问作者rafl