我有一个无向图和无权图的节点的特定子集。我试图确定所有这些节点之间是否有一条路径，如果有，那么最短路径是什么，其中包括不在节点子集中的最少节点。
我一直在想办法修改最小生成树算法来实现这一点，但是到目前为止我还没有找到一个可行的解决方案。
有什么好方法可以做到这一点呢？或者这是对一个已知算法的描述吗？
最佳答案
我想确定这一切之间是否有一条路
节点
（据我所知，您正在寻找访问所有标记节点的单一路径）
好吧，我的朋友，这可能是个问题-你描述的是Traveling Salesman Problem和Hamiltonian Path Problem的变体（如果你在寻找一个简单的路径，那么来自哈密顿路径的reduction是直接向前的：标记所有节点）。
但我担心这些问题是NP-Hard。
NP-难问题是一个不知道任何多项式时间解的问题，一般的假设是-1不存在。
因此，你最好的选择可能是指数解有使用动态规划的tsp的O(n^2 * 2^n)解决方案，或者有O(n!)的强力解决方案。
（1）确实不是一个形式化的定义，但这是足够了解问题的信息，确实有很多np难问题。
关于c# - 连接无向图中某些节点的最短路径，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/12850941/