c++ - 如何找到覆盖有向循环图中所有节点的最短路径？

Question

我需要一个从一个节点到有向循环图的最短路径的例子(它应该从将成为输入的节点到达图中的所有节点)。

如果有示例，我需要用 C++ 编写的，或者算法。

Answer 1

编辑:糟糕，误读了问题。感谢@jfclavette 选择这个。旧答案在最后。

您要解决的问题称为 Travelling salesman problem .有很多potential solutions ，但它是 NP 完全的，因此您无法求解大型图。

旧答案:

您要查找的是 girth的图表。可以通过将节点到自身的距离设置为无穷大并使用 Floyd-Warshall 来解决。算法。从节点i开始的最短循环的长度就是位置ii的条目。