我需要一个从一个节点到有向循环图的最短路径的例子 (它应该从将成为输入的节点到达图中的所有节点)。
如果有示例,我需要用 C++ 编写的,或者算法。
最佳答案
编辑:糟糕,误读了问题。感谢@jfclavette 选择这个。旧答案在最后。
您要解决的问题称为 Travelling salesman problem .有很多potential solutions ,但它是 NP 完全的,因此您无法求解大型图。
旧答案:
您要查找的是 girth的图表。可以通过将节点到自身的距离设置为无穷大并使用 Floyd-Warshall 来解决。算法。从节点i开始的最短循环的长度就是位置ii的条目。
关于c++ - 如何找到覆盖有向循环图中所有节点的最短路径?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/789159/