TenWizards巫师网络最短路：Dijkstra算法在airbnb题库的巧妙应用

TenWizards巫师网络最短路：Dijkstra算法在airbnb题库的巧妙应用

【免费下载链接】airbnb项目地址: https://gitcode.com/gh_mirrors/ai/airbnb

Airbnb 面试题库（airbnb）中的Ten Wizards（十巫师）问题，是 Dijkstra 最短路算法的一道经典实战题：10 位巫师编号 0~9，两人之间通信的成本等于编号差的平方，要求找出从巫师 0 到巫师 9 的最小成本路径。本篇用通俗的方式讲清这道 Airbnb 经典面试题的建模思路、两种解法对比与关键实现细节，帮助新手快速吃透最短路算法。

🧙 问题背景：巫师之间的"通话费"

题目出自 Airbnb 真实面试题，收录在本仓库的 README.md 第 29 题中。规则非常直观：

要素	说明
节点	编号 0~9 的 10 位巫师
边	每位巫师有一个"认识谁"的列表（邻接表）
边权	巫师 i 与 j 通信的成本 = (i − j)²
目标	求 0 → 9 的最小成本路径，并输出路径本身

举个例子：0 认识 1、5、9，5 认识 9，那么走 0 → 5 → 9 的成本是 (0−5)² + (5−9)² = 25 + 16 = 41，这比直连 0 → 9 的 81 便宜得多——多绕一步反而更省钱，这正是需要最短路算法的原因。

🎯 核心思路：为什么必须用 Dijkstra 而不是 BFS

很多新手第一反应是 BFS，但 BFS 只能解决"每步成本相同"的无权图问题。这里边权是编号差的平方（0 到 25 不等），属于典型的带权图最短路问题，Dijkstra 算法才是正解：

1. 起点 0 的代价设为 0，其余巫师初始代价为无穷大
2. 用最小堆反复取出"当前代价最小"的巫师
3. 对其邻居做松弛：如果新代价更优，就更新代价并记录"前驱节点"
4. 堆空后，从目标 9 沿前驱数组一路回溯，即得到最短路径

本仓库中完整实现了两种解法，可以对照学习：

• BFS 朴素版：Solution
• Dijkstra 版（推荐）：Solution_2

两者的差别只有一处：Dijkstra 版把普通队列换成了PriorityQueue最小堆（TenWizards.java#L88-L89），保证每次处理的是代价最小的节点，这是正确性与效率的关键。

🔍 关键实现细节拆解

边权计算：编号差的平方

边权在松弛时即时计算，不预先建图（TenWizards.java#L95）：

int weight = (int) Math.pow(next.id - curr.id, 2);

前驱数组回溯路径

算法只记录最短代价，但要"输出路径"，就得额外维护一个parent数组：每次松弛成功时记下"我是从谁走过来的"（TenWizards.java#L96-L98）。结束后从 9 一路向前跳到 0，再反转列表即可：

while (t != source) { res.add(t); t = parent[t]; } res.add(source); Collections.reverse(res);

Wizard 内部类：代价与比较器

每个巫师封装为Wizard对象，持有id和dist（当前最短代价，初始Integer.MAX_VALUE），并实现Comparable按dist排序，供最小堆使用。详见 Wizard 类定义。

✅ 测试用例：一眼看懂输入输出

单元测试内置了一个 10 个巫师的网络（UnitTest）：

巫师0 → [1, 5, 9] 巫师1 → [2, 3, 9] 巫师2 → [4] 巫师5 → [9] 其余巫师无邻居

从 0 到 9 的候选路径：

路径	成本计算	总成本
0 → 9	81	81
0 → 5 → 9	25 + 16	41✅
0 → 1 → 9	1 + 64	65

测试断言结果恰好是[0, 5, 9]，验证了 Dijkstra 版与 BFS 版都能得出正确答案（test2）。

🚀 最快运行方法：本地跑通单元测试

获取项目：

git clone https://gitcode.com/gh_mirrors/ai/airbnb

进入项目目录后，只运行 Ten Wizards 的测试（要求 Java ≥ 11、Gradle ≥ 5.6.3）：

gradle -Dtest.single=TenWizards test

想跑全部题目测试则直接gradle test。

⚠️ 新手常见坑：BFS 版为什么是"有瑕疵的"

对照阅读时注意：BFS 版 Solution 按入队顺序处理节点，且缺少"已确定最短路的节点不再重复出队"的剪枝，在更复杂的图上是不保证正确的写法；而 Dijkstra 版配合最小堆才能保证每次锁定全局最小代价。学习时建议以Solution_2为标准答案，BFS 版仅用于对比理解。另外pq.remove(next)是 O(n) 操作，面试中更优雅的做法是"出队时检查 dist 是否过期"（惰性删除），可以作为进阶优化点提出来。

📚 延伸学习：题库中的其他图算法题

掌握了 Dijkstra，可以顺手挑战本仓库同类型的图论题：

• 最多 K 站中转的最小机票价格（动态规划最短路变体）：MinimumCostwithAtMostKStops.java
• 最少起点遍历有向图（拓扑相关）：MinimumVerticestoTraverseDirectedGraph.java
• 全部 31 道题目清单与题面描述：README.md

总结：Ten Wizards 是理解"边权 = 节点编号差的平方"这一巧妙设计的绝佳素材——它让"绕远路"变得有利可图，逼迫你用带权最短路算法而非简单 BFS。读懂 TenWizards.java 这一个文件，你就同时收获了 Dijkstra 的完整实现、前驱数组回溯路径的标准套路，以及一份 Airbnb 面试真题的参考答案。

【免费下载链接】airbnb项目地址: https://gitcode.com/gh_mirrors/ai/airbnb