请教巫师这道题

cartmanstart 发表于 2017-5-19 15:25
BFS代码

不讨论正确与否，你这个不是n^2算法吗？

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

我觉得那个可能也有问题，一个是visited更新的时机，另一个是PQ的order要即时update。
其实用PQ写法就应该算是djikstra了吧，我觉得算是这题最优的解法。
但我也不太明白根据这道题具体特征如何优化djikstra(为啥前面说不需要二次更新，照理说应该一定会需要二次更新,比如 dis(1->4->9) < (1->9))，望有大神解答。

bobzhang2004 发表于 2017-5-18 15:11
写了下代码

这个思路挺牛逼的

我觉得也可以直接DFS+backtracking暴力解决，时间复杂度并没想象的高，因为只需要maintain一个到target的cost最小值就可以大大节省时间，如果在DFS当中，发现当前路径的cost已经大于最小值了，直接返回继续做backtracking就好。当然DFS的缺点就是时间复杂度不稳定，如果先走的cost最大的路径直到最后才走cost最小路径，就是worst case.

还是不是很理解BFS的解法，能不能有大神给解释一下. 楼上PriorityQueue的算法应该算是dijkstra的实现，但是BFS这个代码感觉是无限循环了....

补充内容 (2018-9-5 07:48):
不对，我测试了一下写了个类似的思路，好像没问题....

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

foreveryong2017 发表于 2018-9-5 07:59
请问一下 这题 BFS 和 DFS的时间复杂度 是不是一样的啊？ 因为 BFS 也需要 全部 走一遍吧 PQ 你这一层是 ...

看一下dijkstra的原理你就懂了

cartmanstart 发表于 2017-5-19 13:26
dijkstra对这道题有些浪费，因为这道题不用二次更新cost。
要是面试官要求比较高的话，要求你不许用Dijkst ...

你好，请问BFS为什么是线性呢？是线性与边数吗？