TenWizards巫师网络最短路Dijkstra算法在airbnb题库的巧妙应用【免费下载链接】airbnb项目地址: https://gitcode.com/gh_mirrors/ai/airbnbAirbnb 面试题库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、95 认识 9那么走 0 → 5 → 9 的成本是 (0−5)² (5−9)² 25 16 41这比直连 0 → 9 的 81 便宜得多——多绕一步反而更省钱这正是需要最短路算法的原因。 核心思路为什么必须用 Dijkstra 而不是 BFS很多新手第一反应是 BFS但 BFS 只能解决每步成本相同的无权图问题。这里边权是编号差的平方0 到 25 不等属于典型的带权图最短路问题Dijkstra 算法才是正解起点 0 的代价设为 0其余巫师初始代价为无穷大用最小堆反复取出当前代价最小的巫师对其邻居做松弛如果新代价更优就更新代价并记录前驱节点堆空后从目标 9 沿前驱数组一路回溯即得到最短路径本仓库中完整实现了两种解法可以对照学习BFS 朴素版SolutionDijkstra 版推荐Solution_2两者的差别只有一处Dijkstra 版把普通队列换成了PriorityQueue最小堆TenWizards.java#L88-L89保证每次处理的是代价最小的节点这是正确性与效率的关键。 关键实现细节拆解边权计算编号差的平方边权在松弛时即时计算不预先建图TenWizards.java#L95int 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 → 981810 → 5 → 925 1641✅0 → 1 → 91 6465测试断言结果恰好是[0, 5, 9]验证了 Dijkstra 版与 BFS 版都能得出正确答案test2。 最快运行方法本地跑通单元测试获取项目git clone https://gitcode.com/gh_mirrors/ai/airbnb进入项目目录后只运行 Ten Wizards 的测试要求 Java ≥ 11、Gradle ≥ 5.6.3gradle -Dtest.singleTenWizards 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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 TenWizards巫师网络最短路：Dijkstra算法在airbnb题库的巧妙应用
TenWizards巫师网络最短路Dijkstra算法在airbnb题库的巧妙应用【免费下载链接】airbnb项目地址: https://gitcode.com/gh_mirrors/ai/airbnbAirbnb 面试题库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、95 认识 9那么走 0 → 5 → 9 的成本是 (0−5)² (5−9)² 25 16 41这比直连 0 → 9 的 81 便宜得多——多绕一步反而更省钱这正是需要最短路算法的原因。 核心思路为什么必须用 Dijkstra 而不是 BFS很多新手第一反应是 BFS但 BFS 只能解决每步成本相同的无权图问题。这里边权是编号差的平方0 到 25 不等属于典型的带权图最短路问题Dijkstra 算法才是正解起点 0 的代价设为 0其余巫师初始代价为无穷大用最小堆反复取出当前代价最小的巫师对其邻居做松弛如果新代价更优就更新代价并记录前驱节点堆空后从目标 9 沿前驱数组一路回溯即得到最短路径本仓库中完整实现了两种解法可以对照学习BFS 朴素版SolutionDijkstra 版推荐Solution_2两者的差别只有一处Dijkstra 版把普通队列换成了PriorityQueue最小堆TenWizards.java#L88-L89保证每次处理的是代价最小的节点这是正确性与效率的关键。 关键实现细节拆解边权计算编号差的平方边权在松弛时即时计算不预先建图TenWizards.java#L95int 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 → 981810 → 5 → 925 1641✅0 → 1 → 91 6465测试断言结果恰好是[0, 5, 9]验证了 Dijkstra 版与 BFS 版都能得出正确答案test2。 最快运行方法本地跑通单元测试获取项目git clone https://gitcode.com/gh_mirrors/ai/airbnb进入项目目录后只运行 Ten Wizards 的测试要求 Java ≥ 11、Gradle ≥ 5.6.3gradle -Dtest.singleTenWizards 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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考