无向图中连接特定节点的最短路径

Question

我有一些无向且无权图的节点子集。我想确定所有这些节点之间是否存在路径，并且如果存在，最短的路径应该包含尽可能少的不在节点子集中的节点。

我一直在尝试想出一种修改最小生成树算法来实现这个目标，但是迄今为止我还没有想出可行的解决方案。

有没有好的方法来解决这个问题，或者已经存在某种已知的算法可以用来解决这个问题？

- user1736516

Answer 1

这是一种可能能帮助你达到目的的方法：

使用 Floyd-Warshall 或 Dijkstra 算法来找出每个 i 和 j 节点之间的距离 d(i, j)，其中节点 i 和节点 j 都在节点子集中。

（如果 d(i, j) = 无穷大，那么现在停止，没有解决方案）

创建一个包含子集中每个节点的新图。对于每个 d(i, j)，在新图中添加连接节点 i 和节点 j 的边，权重为 d(i, j)。

现在，在这个新图上使用旅行商算法来找到访问所有节点的最短路径。

这条最短路径给出了路径长度，但是路径可能会多次访问某些节点。这意味着我们对需要的子集外部节点数量有一个上限。

- Rusty Rob

---

谢谢您的回复。您介意详细说明一下这个如何工作吗？在第二步中，对于子集中的每个节点创建一个新图时，其他需要连接子集中节点但不属于子集的节点应该怎么处理？ - user1736516

我刚意识到我的方法只获取了路径的长度，但没有获取路径中包含哪些节点。为了澄清，d(i, j) 是节点i和节点j之间不在子集中的节点数。i,j之间的边表示这条路径（但我们不关心路径中的那些节点，所以将其表示为单个边）。然后你得到最小生成树。这给出了最短路径的长度。但它并没有告诉你路径在哪里。现在你需要找到一条路径，使得子集外的节点重叠最大化。 - Rusty Rob

真的。我编辑了我的答案。不确定为什么我提到了MST而不是TSP。您可以使用MST来近似解决TSP问题，该解决方案的精度在两倍以内。 - Rusty Rob

我仍然不确定解决方案。建议的方法仍存在问题：（1）返回的路径可能不是简单路径（外部节点将被使用两次）。 （2）如果我们正在寻找非简单路径-OP说：“包括最少不在节点子集中的节点的最短路径”。这意味着一个被使用两次的节点只计算一次。 - amit

我不认为继续这个讨论有任何意义——重点已经很明确了，一个人应该明白自己在寻找什么。如果你试图最小化不在子集中的节点数量，或者这只是一个次要的标准，那么评论讨论已经足够说明这个问题，并得出结论，究竟需要什么。如果是后者，解决方案至少应该是一个很好的起点，当然前提是你能接受非简单路径。 - amit

Answer 2

我正在尝试确定是否存在连接所有这些节点的路径。（我理解您正在寻找访问所有标记节点的单一路径）

好吧，我的朋友，这可能是个问题——您正在描述旅行商问题和哈密顿路径问题的变体（如果您正在寻找简单路径，则从哈密顿路径的简化很直接：标记所有节点）。但恐怕这些问题是NP难问题。

NP难问题是一个我们没有任何多项式时间解决方案来解决它的问题，并且普遍的假设是——不存在这样的解法¹。

因此，你最好的选择可能是一些指数解法。使用动态规划有一个O(n^2 * 2^n)的TSP解法，或者是暴力解法，其复杂度为O(n!)。

---

真的不是一个正式的定义，但这已经足够了解这个问题，NP-困难问题还有很多更多的内容。

- amit

---

我同意“标记所有节点”的做法。如果存在长度为n-1的路径，则最小化最短路径是一条哈密顿路径。 - Rusty Rob

Answer 3

我创建了一个图/节点/连接类，不仅可以显示最短路径，还可以告诉您所有节点是否连接：

var allNodesAreConnected = StartNode.AllNodes.All(n => n.IsConnectedToStartNode);

或者如果你想知道哪些节点没有连接，稍微改变一下：

var anotConnectedNodes = StartNode.AllNodes.Where(n => !n.IsConnectedToStartNode);

更多示例和完整代码请参见本文： 创建您自己的导航系统（使用图形、节点和连接类）

- Alex Siepman

Answer 4

对于一个没有图论背景的人来说，我解决了这个问题，并发现在一个无权、无向图中，最简单的方法是深度优先搜索。像Dijkstra这样的算法实现通常采用加权解决方案，并为权重输入任意值。

我找到的解决方案是使用DFS遍历节点并记录每次成功的旅程，然后只需返回最短的成功旅程即可。

这里是执行重要任务的文件： 深度优先搜索算法

- Steve Westwood

Answer 5

使用Dijkstra算法或广度优先搜索。

- iefpw

---

无法解决：“我正在尝试确定所有这些节点之间是否存在路径。” - amit

Answer 6

您应该使用狄克斯特拉最短路径算法。首先，您必须为图中的所有边分配权重（或距离），连接两个不在子集中的节点的每条边都必须赋予权重1。将连接子集中一个或两个节点的每条边都赋予无限权重。其次，您应该在结果图上运行狄克斯特拉算法。 此算法将检查图的每条边。

此外，您还可以使用A*（A星）算法。

更新： 我一开始并不理解这个问题。正如@amit所说，这是一个NP难题，HCP和TSP的组合。也许某种随机搜索算法可以在多项式时间内以高概率解决这个问题。

- Evgeny Lazin

---

两者都是到单个顶点的最短路径，路径没有限制（除了最短）。它不能解决“我正在尝试确定所有这些节点之间是否存在路径”的问题。 - amit