访问图中所有节点的最短路径(状态压缩 BFS)
哪些公司问过
答案要点
- 先明确是点对最短路,还是访问所有节点的最短路线
- 状态为(当前节点,已访问位掩码),多源同时入队
- visited[节点][掩码] 去重,首次掩码全满即得答案
- 时间 O(n² × 2^n),只适合节点数较少的图
- 有权图:Floyd 预处理距离后做旅行商式状压 DP
易错点
- 只按节点去重,导致无法回头走
- 只从一个固定起点出发,题目却允许任意起点
- 节点多时仍用状态压缩,状态数爆炸
面试官常见追问
- 如果只是求两点间最短路,用什么算法?
- 为什么不能只用节点做 visited?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。