在这一章,我们学习了 Dijkstra 算法。Dijkstra 算法用来解决带权图的最短路径问题(无负权)。
在这个课程之前,我们学习了如何解决无权图的最短路径问题:BFS。
实际上,如果大家仔细比较,就会发现,这两个算法在结构上是有共同之处的。BFS 的核心是一个队列;而对于带权图,因为每条边有权值了,所以一个简单的队列不够了,我们需要一个优先队列。
在这里,我希望大家能够仔细地比较 BFS 算法和 Dijkstra 算法的思路,仔细体会这二者的异同。看看大家能不能体会出来,Dijkstra 算法,其实是 BFS 算法在有权图上的拓展。为了解决带权边,加入了一些东西,但是,整体算法的思路是一致的。
如果大家真的深刻理解了这个异同,如果大家能白板写出 BFS 算法的话(计算机专业的同学应该具备这个能力),大家也应该能够轻易白板写出 Dijkstra 算法。
你能体会到 BFS 和 Dijkstra 之间的区别和联系吗?有什么感想?可以在这里分享一下?
大家加油!:)