访问所有节点的最短路径

Question

我正在寻找一种算法，它对我来说似乎非常典型，但似乎常见的解决方案都不太一样。

在一个无向图中，我想要访问每个节点的最短路径。节点可以重复访问，而且我不必返回起点。

旅行商问题似乎增加了每个节点只能被访问一次并且路径必须返回到起点的限制。

最小生成树可能是解决方案的一部分，但这种算法只提供了树形结构，而不是最小路径。此外，由于它们是树形结构且没有环路，所以强制回溯，在某些情况下可能更有效的是使用环路。

- MyiEye

Answer 1

您可以通过对图进行转换，将其简化为普通的旅行商问题。

首先，计算每对节点之间的最小距离。您可以使用 Floyd-Warshall 算法来计算。一旦您得到它，只需构造完整的图，其中节点 u 和 v 之间的边是从 u 到 v 的最小成本。

然后，您可以应用常规的 TSP 算法，因为您不必再次访问节点，这已经隐藏在边缘的成本中了。

- AlexAlvarez

---

听起来不错。我编辑了我的问题，让一个点更加清晰，即TSP涉及返回起点，这对我也不是必需的。 - MyiEye

考虑不需要重新访问节点的情况，但不能保证它结束于起点。 - Lawrence Weru

Answer 2

我们可以使用修改后的BFS算法。

基本上在BFS期间从任何节点开始，我们需要能够遍历已经访问过的节点，但是我们如何确保我们不会形成无限循环呢？

我们为每个节点存储“所有”节点的访问状态。这意味着，如果我们已经走过节点1，并且我们需要再次穿过它，只要我们之前没有见过“所有”节点的总状态，我们就可以这样做。这就是位掩码的原因，而不是简单的整数集合。请注意，您也可以使用字符串集合来存储状态，但运行速度较慢。

    public int shortestPathInSmallGraph(int[][] graph) {
        if (graph.length == 1) {
            return 0;
        }
        Set<Integer>[] adj = new HashSet[graph.length];
        int n = graph.length;
        int endState = (1 << n) - 1;
        boolean[][] seen = new boolean[n][endState];
        Queue<int[]> queue = new ArrayDeque<>();
        
        for (int i = 0; i < n; i++) {
            queue.add(new int[] {i, 1 << i});
            seen[i][1 << i] = true;
        }
        int steps = 0;
        while (!queue.isEmpty()) {
            int count = queue.size();
            for (int i = 0; i < count; i++) {
                int[] pair = queue.poll();
                int node = pair[0];
                int state = pair[1];
                for (int neighbor : graph[node]) {
                    int nextState = state | (1 << neighbor);
                    if (nextState == endState) {
                        return 1 + steps;
                    }
                    
                    if (!seen[neighbor][nextState]) {
                        seen[neighbor][nextState] = true;
                        queue.add(new int[] {neighbor, nextState});
                    }
                }
            }
            steps++;
        }
        return -1;
    }

- Harry