二分+BFS能取代Dijkstra算法吗？

来源：12-6 Dijkstra 和 BFS 的联系

讲武德的年轻人

2022-06-13

请问波波老师，如果我们只关心最短路径的长度（而不是路径本身），是不是也可以用二分搜索+BFS实现呢？相当于先猜一个最短长度，用BFS验证是否能够走得通；如果可以走得通，继续缩小上界进行BFS。如果可行的话，是不是时间复杂度跟Dijkstra算法类似呢？在log级别上可能时间复杂度上稍高，但是应该差距不大。谢谢老师！

写回答

1回答

liuyubobobo

2022-06-13

关键是你猜一个最短长度以后，如何用 BFS 验证？

你可以把你的设想用代码表示出来。然后随便找一个平台上的 dijkstra 的问题验证你的想法。

另外，dijkstra 的优势不仅仅是求出两点间的最短路径，而是直接求出了“单源最短路径”。单源最短路径的意思是，求出了从一个点 s 到图上所有点的最短路径。但是你的思路（假设是work的），只求出了两点的最短路径。如果要求从一点到图中所有点的最短路径，还要再乘以一个 V，复杂度妥妥超 dijkstra。

继续加油！：）

玩转算法系列--图论精讲（Java版）

30+小时系统学习，bobo带你克服被图论支配的恐惧

1591 学习 · 324 问题

查看课程

相似问题

二分+BFS解决leetcode 505的问题

回答 1

优先队列的另一种写法

回答 1

能否用BFS进行有向图环检测

回答 1

【JS】根据老师讲解Dijkstra算法的模拟过程思路，自己实现了Dijkstra算法。

回答 1

可以用dfs代替bfs吗

回答 1

打开慕课网App查看更多内容