Dijkstra 和 BFS 的联系
772
等3人参与

在这一章,我们学习了 Dijkstra 算法。Dijkstra 算法用来解决带权图的最短路径问题(无负权)。

在这个课程之前,我们学习了如何解决无权图的最短路径问题:BFS。

实际上,如果大家仔细比较,就会发现,这两个算法在结构上是有共同之处的。BFS 的核心是一个队列;而对于带权图,因为每条边有权值了,所以一个简单的队列不够了,我们需要一个优先队列。

在这里,我希望大家能够仔细地比较 BFS 算法和 Dijkstra 算法的思路,仔细体会这二者的异同。看看大家能不能体会出来,Dijkstra 算法,其实是 BFS 算法在有权图上的拓展。为了解决带权边,加入了一些东西,但是,整体算法的思路是一致的。

如果大家真的深刻理解了这个异同,如果大家能白板写出 BFS 算法的话(计算机专业的同学应该具备这个能力),大家也应该能够轻易白板写出 Dijkstra 算法。

你能体会到 BFS 和 Dijkstra 之间的区别和联系吗?有什么感想?可以在这里分享一下?

大家加油!:)


我的作业
去发布

登录后即可发布作业,立即

全部作业

数据加载中...

意见反馈 帮助中心 APP下载
官方微信