时间戳

首页 > 解决方案 > 给定一组可能的起始节点，找到访问某些节点并返回的最小路径

algorithm - 给定一组可能的起始节点，找到访问某些节点并返回的最小路径

问题描述

我有一组节点（<= 10,000）和边（<= 50,000），它们通过某种组合将它们连接起来。也就是说，您可以使用至少一种边组合从任何其他节点开始访问任何节点。边定义了它们的长度。

为我提供了一组必须通过的节点（最多 5 个）。所有这些都必须访问，如果需要，我们可以多次通过它们。我们需要从不是必须通过的节点之一开始我们的旅程，访问所有必须通过的节点，然后返回到我们的初始节点。

我们需要找到这样一条路径的最短距离。

假设我们有 5 个索引节点1, 2, 3, 4, 5和以下格式的边node -> node : length（全部无向）：

1 -> 2 : 1
1 -> 5 : 2
3 -> 2 : 3
3 -> 4 : 5
4 -> 2 : 7
4 -> 5 : 10

并且必须通过的节点是1, 2, 3. 当我们从节点 5 开始时，我们的最短距离可以实现，路径如下：5-1-2-3-2-1-5，因此行进距离为12。12是我们想要的输出。

有没有一种有效的方法来解决这个问题？

标签： algorithmgraph-theory

解决方案

这是 O(E log V) 解决方案：

  1. 让我们将起始节点视为必须通过的节点
  2. 使用 Dijkstra 找到所有“必须通过”节点对之间的最短路径
  3. 现在问题简化为 6 个城市的旅行推销员问题
  4. 我们可以在 O(6!) 时间内检查所有排列，也可以对 O(2^6 * 6^2) 使用动态编程，因为 6 是一个常数，这部分复杂度为 O(1)

推荐阅读