图中遍历所有节点的最短路径

1. 概述

在本教程中，我们将讨论如何在图中找到一条遍历所有节点的最短路径。

我们将首先明确问题定义并给出一个示例。随后，介绍两种不同的解决方案：暴力法和基于 Dijkstra 的状态压缩法。

2. 问题定义

给定一个图 $ G $，其中包含 $ V $ 个节点（编号从 $ 0 $ 到 $ V - 1 $）和 $ E $ 条带权边。我们的任务是找出一条路径，遍历所有节点，并使该路径的总权重最小。

需要注意的是：

我们可以重复访问节点
路径的起点和终点可以是任意节点
所求路径是所有满足“遍历所有节点”条件的路径中总权重最小的那一个

来看一个示例：

WeightedGraph

上图中，遍历所有节点的最短路径为：
0 → 1 → 4 → 1 → 2 → 3，总权重为 6。

3. 暴力法

3.1. 核心思想

枚举所有节点的排列顺序
每个排列表示一个访问顺序
使用 Floyd-Warshall 算法预处理任意两点间的最短路径
对每个排列，计算路径总权重，取最小值作为答案

3.2. 实现代码

algorithm BruteForceApproach(V, G):
    // INPUT
    //     V = the number of nodes in the graph
    //     G = the graph stored as an adjacency list
    // OUTPUT
    //     Returns the shortest path visiting all nodes in G

    answer <- infinity
    distance <- Calculate_Floyd_Warshall(G) // a matrix
    permutations <- Calculate_Permutations()

    for permutation in permutations:
        cost <- 0
        previous <- permutation[0]
        for node in permutation:
            cost <- cost + distance[previous, node]
            previous <- node
        if cost < answer:
            answer <- cost

    return answer

3.3. 时间复杂度分析

Floyd-Warshall：$ O(V^3) $
所有排列数量为 $ V! $，每个排列遍历需要 $ O(V) $
总时间复杂度：**$ O(V^3 + V \times V!) $**

⚠️ 该方法仅适用于 $ V \leq 10 $ 的小规模图，否则计算量爆炸

4. Dijkstra 状态压缩法

4.1. 核心思想

使用 Dijkstra 算法的变种，结合状态压缩（bitmask）来表示已访问的节点集合：

每个状态用 (当前节点, 已访问节点集合) 表示
初始时，每个节点作为起点，其 bitmask 只有对应位为 1
使用优先队列进行松弛操作，逐步更新状态
最终答案为所有节点中，bitmask 全为 1 时的最小代价

✅ 优点：相比暴力法，大大减少了无效路径的计算
❌ 缺点：空间复杂度较高，适用于 $ V \leq 16 $ 的情况

4.2. 实现代码

algorithm DijkstraApproach(V, G):
    // INPUT
    //     V = the number of nodes in the graph
    //     G = the graph stored as an adjacency list
    // OUTPUT
    //     Returns the shortest path visiting all nodes

    cost <- a matrix whose all entries are infinity
    priority_queue <- make an empty priority queue
    for node from 0 to V-1:
        priority_queue.add(node, 2^node)
        cost[node, 2^node] <- 0

    while priority_queue is not empty:
        current <- priority_queue.front().node
        mask <- priority_queue.front().bitmask
        priority_queue.pop()
        for child in G[current]:
            add <- weight(current, child)
            if cost[child, mask or 2^child] > cost[current, mask] + add:
                priority_queue.add(child, mask or 2^child)
                cost[child][mask or 2^child] <- cost[current][mask] + add

    answer <- infinity
    for node from 0 to V-1:
        answer <- min(answer, cost[node, 2^V - 1])

    return answer

4.3. 时间复杂度分析

状态总数为 $ V \times 2^V $
每次状态入队出队操作为 $ O(\log(V \times 2^V)) $
总时间复杂度：**$ O(V \times 2^V \times \log(V \times 2^V)) $**

5. 总结

我们讨论了图中遍历所有节点的最短路径问题，并提供了两种解决方案：

方法	时间复杂度	适用场景
暴力法	$ O(V^3 + V \times V!) $	$ V \leq 10 $
Dijkstra + Bitmask	$ O(V \times 2^V \times \log(V \times 2^V)) $	$ V \leq 16 $

✅ 推荐使用第二种方法，尤其在节点数稍多时优势明显
⚠️ 注意空间开销，合理设置状态数组大小

Persistence

REST

Security